Assumption: you're running on an Apache web server. If not, you'll have to translate the relevant portions of this answer into the nginx or IIS or whatever server-ese.
Per the Codex page on setting up Multisite, you should have Pretty Permalinks enabled and working on your site prior to setting up Multisite. (See Step 1.) Pretty Permalinks require you to set up rewrite rules in a .htaccess
file (or else in your server's config file).
Proper .htaccess
files (as mentioned by @user42826 in his/her answer) depend on the version of WordPress you're starting from. Since the current version is 4.0, I'm going to assume that's what you're dealing with.
.htaccess
file for WP Multisite > 3.5:
RewriteEngine On
RewriteBase /
RewriteRule ^index\.php$ - [L]
# add a trailing slash to /wp-admin
RewriteRule ^([_0-9a-zA-Z-]+/)?wp-admin$ $1wp-admin/ [R=301,L]
RewriteCond %{REQUEST_FILENAME} -f [OR]
RewriteCond %{REQUEST_FILENAME} -d
RewriteRule ^ - [L]
RewriteRule ^([_0-9a-zA-Z-]+/)?(wp-(content|admin|includes).*) $2 [L]
RewriteRule ^([_0-9a-zA-Z-]+/)?(.*\.php)$ $2 [L]
RewriteRule . index.php [L]
If you're using a version older than 3.5 (and if you are, please upgrade), then check out this page for alternate .htacess
rules.
Edit -- it looks like you've got the .htaccess
rules for versions lower than 3.5 (ie, 3.4.2 or earlier). If you've upgraded your WordPress Multisite installation from 3.4.2 or earlier to 4.0, that should work. If you've been running WordPress single-site since before 3.4.2, you should read this:
You cannot choose Sub-directory Install (for a path-based network) if your existing WordPress installation has been set up for more than a month, due to issues with existing permalinks.
From the Restrictions section on the Before You Create a Network page.