Объясню детальнее, т.к. вопрос вижу частый


1. Важно какие физически данные хранятся в таблице, это зависит от того как они туда попали (что было в INSERT, какая кодировка соединения была при INSERT или откуда была получена БД, например из старой версии MySQL). Посмотреть как выглядят символы можно открыв *.MYD файл в текстовом редакторе, если в блокноте есть читабельный текст - значит 1251, если непонятные символы - UTF8

2. Важно какая кодировка присвоена текущему конекту к БД. Посмотреть её можно выполнив SHOW VARIABLES LIKE '%char%' и SHOW VARIABLES LIKE '%collat%'

3. Важно какая для текущего столбца присвоена в описании кодировка. Посмотреть можно SHOW CREATE TABLE tbl_foo;

Чтобы всё нормально работало, в п.1.2.3 кодировки должны совпадать.

1. Если неправильная кодировка внутри, то надо сделать

ALTER TABLE foo CONVERT TO CHARACTER SET cp1251 COLLATE cp1251_ukrainian_ci;

Но надо убедиться что в текущем описании таблицы (п.3.) стоит правильное описание текущей кодировки, если скажем физически лежит UTF8, а в описании числится latin1, то при конвертации будут применены правила latin1->cp1251 и получится фигня.

2. Изменять кодировку для соединения можно:
а) явно в каждом конекте через комманды
SET character_set_client =foo
SET character_set_results =foo
SET character_set_connection=foo

эти команды можно дать проще:
а1) Макрос "SET NAMES foo"
а2) Макрос "SET CHARACTER SET foo" (collation будет задаваться не явно, а от выбранной mysql_select_db)

б) указать административно на сервере my.cnf:
skip-character-set-client-handshake
init-connect="SET CHARACTER SET cp1251"

3. Изменять описание таблицы можно через ALTER TABLE или перезаливкой дампа таблицы с правильным CREATE TABLE

Ещё следует иметь ввиду, что в случае, когда при создании баз (CREATE DATABASE), создании таблиц (CREATE TABLE) и создании столбцов (ALTER TABLE) если ЯВНО не указать кодировку для описания, будет применена родительская, для БД - дефолтная сервера, для таблицы - дефолтная БД, для столбца - дефолтная таблицы.
Это влияет на импорт дампа без четкого указания кодировки:
CREATE TABLE ... ENGINE=MyISAM DEFAULT CHARSET=utf8

Поменять дефолтный серверный чарсет и колейшен можно в my.cnf:

character_set_server = cp1251
collation_server = cp1251_ukrainian_ci

Тогда неявно созданные DATABASE будут иметь именно эту кодировку и сравнение.

К пункту 1, детальнее насчет того в какой кодировке сейчас лежат данные.

А. Если папку datadir взять из старой версии MySQL 4.0/3.23 и просто подложить в MySQL 4.1, то автоматически в БД information_schema будет прописана каждой БД и каждой таблице дефолтная кодировка, каждому столбцу присвоена кодировка.
По умолчанию сервер MySQL скомпилирован с дефолтной кодировкой сервер latin1_swedish_ci. Это значит что если лежали данные в кодировках отличных от latin1, то будет форсировано значение latin1 и нарушена правильная работа. Если потом попытаться изменить через ALTER TABLE на правильную (например CP1251) то физические данные вообще нарушатся (к ним будет применено правило перекодирования ISO-8859-1 => CP1251). Поэтому ВАЖНО, при миграции datadir в MySQL 4.1+ прописать в my.cnf:

[mysqld]
character_set_server = cp1251
collation_server = cp1251_ukrainian_ci

или другую кодировку, которая раньше у вас употреблялась в качестве default_character_set

Б. Имеется SQL-дамп БД. Надо определить в правильной ли он кодировке, совпадают ли физические данные в значениях строк с таковыми указанными в CREATE TABLE .. для каждого столбца, или если в описании столбцов нету - какие присвоены дефолтные для таблицы
CREATE TABLE ... ENGINE=MyISAM DEFAULT CHARSET=KOI8-R

Убедитесь что они совпадают, если не совпадают то можно подправить через Find/Replace на нужные в описании таблицы или прогнать файл через конвертор, например iconv("текущая", "нужная")

Если дамп получен из MySQL 4.0/3.23 то в нем не будет ничего о кодировках таблиц/столбцов. При попытке его импорта для таблиц будет форсировано значение дефолтной кодировки БД (в случае создания БД через админпанель хостера база будет создана с дефолтной кодировкой сервера, по умолчанию latin1)

Поэтому ВАЖНО!! При импортировании дампов из MySQL 4.0/3.23 дописать через Find/Replace нужную кодировку
CREATE TABLE ... ENGINE=MyISAM DEFAULT CHARSET=KOI8-R

В. Надо получить дамп
а) mysqldump
--default-character-set=name [Set the default character set]
Допишет к каждой таблице CREATE TABLE ... ENGINE=MyISAM DEFAULT CHARSET=name
б) phpMyAdmin
данные экспортируются в той кодировке в которой лежат и описание таблиц как есть. Если надо что-то изменить - то изменить в таблице (ALTER TABLE)

Г. Надо залить дамп
а) mysql < log.sql
надо убедиться что текущий
SET character_set_client =foo
SET character_set_results =foo
SET character_set_connection=foo
такой же как в дампе. Его можно изменить добавив первой строкой дампа нужный SET NAMES foo или SET character_set_client =foo
mysqldump по умолчанию добавляет SET NAMES, изменить можно через --set-charset foo, отключить добавление в дамп можно через --skip-set-charset

Если не указывать явно в дампах, можно в my.cnf добавить в секцию [mysql]
init-connect="SET CHARACTER SET foo" или
init-connect="SET NAMES foo"

б) phpMyAdmin (или другой PHP клиент), надо убедиться что при импорте используется нужная кодировка. phpMyAdmin требует указывать кодировку импортируемых дампов, он сам делает SET NAMES foo
Если скрипт сам не делает SET NAMES foo, то применяется NAMES вкомпилированный в клиентскую библиотеку libmysql (utf8)
Если подправить скрипт и дописать mysql_query("SET NAMES ...") не представляется возможным, есть административный метод
my.cnf:

[mysqld]
skip-character-set-client-handshake
init-connect="SET CHARACTER SET cp1251"

К теме изменения кодировок Изменение кодировки таблиц в MySQL
Перечень ссылок, которых достаточно для решения вопросов с кодировками в MySQL Проблема с кодировками в MySQL

Это может быть достаточно проблемно сделать если таблиц много а столбцов ещё больше (у каждого свой тип и своя длина).

Я предлагаю такой вариант:

mysqldump.exe -u my_user -p --default-character-set=latin1 -t база > дамп.sql

Где вместо latin1 надо подставить неправильную кодировку которая совпадает с прописанной в описаниий столбцов (когда они совпадут не будет конверсия данных и в дампе получим нормальные данные в той кодировке в какой они лежат в MYD файле)

Потом очищаем таблицы или создаем наново с правильными дефолтными кодировками и вставляем дамп.