Almacenar palabras con tildes en MySQL y mostrarlas en el navegador

[weltxo]

Hola amigos, me encuentro con un pequeño problema que me está quitando muchas horas. He leído numerosos mensajes sobre el famoso tema de las tildes y los caracteres extraños, y sigo sin poder dar con la solución.

Tengo un formulario, y quiero, que el usuario teclee en un input text (por ejemplo, "Gijón"), y al pulsar sobre el submit, se almacene el valor "Gijón" en la base de datos y muestra un mensaje "Ha introducido Gijón en la base de datos".

Me interesa guardar los valores exactamente con las tildes, porque tengo un pequeño buscador hecho en AJAX que busca los valores, de modo que si guardo en MySQL "Gijón" y tecleo en el buscador "Gijón" no aparece el resultado.

He probado a cambiar los cotejamientos de las tablas, el charset de los navegadores, pero no consigo solucionarlo y ya no sé qué más hacer. Espero vuestra ayuda. Gracias !