First First, backup!
First, you need to set the default char sets on the database. This does not convert existing tables, it only sets the default for newly created tables.
ALTER DATABASE dbname CHARACTER SET utf8 COLLATE utf8_general_ci;
Then, you will need to convert the char set on all existing tables and their columns. This assumes that your current data is actually in the current char set. If your columns are set to one char set but your data is really stored in another then you will need to check the MySQL manual on how to handle this.
ALTER TABLE tbl_name CONVERT TO CHARACTER SET utf8 COLLATE utf8_general_ci;
Some Usefull snippets
ALTER DATABASE databasename CHARACTER SET utf8 COLLATE utf8_unicode_ci;
ALTER TABLE tablename CONVERT TO CHARACTER SET utf8 COLLATE utf8_unicode_ci;