Связь многие ко многим.
Есть таблица записей. Есть таблица категорий. Создаешь еще одну таблицу с двумя полями.
post_id / cat_id
туда пихаешь привязку для каждой категории.
Открой учебник по mysql и найдешь кучу примеров как с эти работать.
к примеру как определить категории к которым принадлежит запись
PHP:
select * from categories, cat_post where cat_post.post_id= $post_id and categories.id=cat_post.cat_id