вам НУЖНО указать, какой набор символов базе использовать для хранения. кодировку можно указывать для базы, таблиц, столбцов. соответственно кодировка указанная для столбца перекрывает указанную для таблицы и т.п.
для создания базы используем такой синтаксис:
CREATE DATABASE db_name DEFAULT CHARACTER SET cp1251 DEFAULT COLLATE cp1251_general_ci
если база уже есть, и таблицы уже есть, то можно сменить указанную таблицам кодировку на нужную. при этом можно это сделать двумя путями:
а) когда кодировка соответствует данным, но вы хотите, чтобы кодировка изменилась, и изменилась вместе с данными:

для базы: ALTER DATABASE db_name DEFAULT CHARACTER SET cp1251 DEFAULT COLLATE cp1251_general_ci
для таблицы: ALTER TABLE tbl_name DEFAULT CHARACTER SET cp1251 COLLATE cp1251_general_ci

б) кодировка у таблицы указана неверно, а данные уже там:

ALTER TABLE t1 CHANGE c1 c1 BLOB, CHANGE c2 c2 BLOB; ALTER TABLE t1 CHANGE c1 c1 TEXT CHARACTER SET cp1251, CHANGE c2 c2 TEXT CHARACTER SET cp1251;
ну понятно, что вместо TEXT вам нужно указать ваш тип столбца.
Внимание: boda тут подметил, что на старых версиях вроде 4ки, если у вас фиксированые поля, например char (а не варчар), то конвертация в blob тихим сапом превратит char в varchar. есть несколько вариантов этого избежать, например конвертить не в блоб, а в binary. но там свои нюансы. в общем посовещавшись мы пришли к выводу, что лучше всего конвертить вышеуказанным способом, НО все столбцы таблицы одним запросом. в этом случае и в 4ке всё работает.

дамп по-умолчанию делается в utf8. но у вас может быть дамп в какой угодно кодировке. поэтому мы должны первым делом сообщить mysqld в какой кодировке у нас данные. для этого мы первой строкой вставляем в дамп: set names cp1251

cp1251 заменяем на название кодировки, которую имеют ваши данные. это гарантирует нам успешную заливку данных.
надо ещё добавить, что неплохо бы проверить, что в описаниях баз и таблиц в дампе указана нужная вам кодировка, как описано в пункте №1.

все эти три переменные могут быть выставлены одной командой: set names cp1251. эту команду следует посылать сразу после коннекта первой строкой, переменные сохранятся в нужном нам состоянии до закрытия коннекта.
если есть доступ к конфигу сервера (my.cnf на *nix и my.ini под виндой), то можно выставить переменные сразу в нём для всех клиентов. делаем это так:

находим там секцию [client] и добавляем туда:
default-character-set = cp1251
character-sets-dir = /usr/local/mysql4/share/charsets

где первое нужная вам кодировка, а второе путь до папки с ними.

находим там секцию [mysqld] и добавляем туда:
default-character-set=cp1251

находим (или добавляем, если нету) секцию [mysql] и добавляем туда:
default-character-set=cp1251

не забываем пеерзагрузить сервер.
проверить, что кодировка теперь выставлена можно выполнив команды:

SHOW VARIABLES LIKE 'character_set%';
SHOW VARIABLES LIKE 'collation%';