How should I store multiple relationships (many posts to many categories)? I have posts stored in a posts table and I want each post to have multiple categories, what is the most efficient way to store the categories and their relationships ?

I thought of it this way first:

Categories Table:

+------------+---------------+------+-----+---------+----------------+
| Field      | Type          | Null | Key | Default | Extra          |
+------------+---------------+------+-----+---------+----------------+
| id         | int(11)       | NO   | PRI | NULL    | auto_increment |
| name       | varchar(32)   | NO   |     | NULL    |                |
| parent     | int(11)       | NO   |     | NULL    |                |
+------------+---------------+------+-----+---------+----------------+

Relationships Table:

+------------+---------------+------+-----+---------+----------------+
| Field      | Type          | Null | Key | Default | Extra          |
+------------+---------------+------+-----+---------+----------------+
| post_id    | int(11)       | NO   |     | NULL    |                |
| cat_id     | int(11)       | NO   |     | NULL    |                |
| order      | int(11)       | NO   |     | NULL    |                |
+------------+---------------+------+-----+---------+----------------+


Using this structure I will have lots of rows inside the relationships table, for example if a post has 4 categories I will have 4 rows only for this post, of course I won't have that much categories related to the post but I want to implement the same structure for tags too.

Am I doing it right ? is there a better structure to use ?
The way that you have described it is the way to do it.  The Primary key for this table is Post_Id, Cat_ID.