How to remove “index.php” from URLs?

Hello.

My site, http://www.evernightfan.com, is being a pain.

I want all of my permalinks to just be “www.evernightfan.com/media”, etc. However, unless I make it “www.evernightfan.com/index.php/media”, I get this sort of error:

Not Found
The requested URL /site/ was not found on this server.

Additionally, a 404 Not Found error was encountered while trying to use an ErrorDocument to handle the request.
Apache/1.3.41 Server at http://www.evernightfan.com Port 80

I’ve made my .htaccess file rewritable; in my Permalink Settings, I’ve chosen Custom Structure, and in the space put it /%postname%/; in the general settings, my WordPress address (URL) and Blog address (URL) are like this: http://www.evernightfan.com.

I’m not sure what to do. I read in the 5 Minute Install page on WordPress that I should use some sort of Apache module mod_rewrite thing, etc., but I have no idea how to do that or what that even is.

Any help would be appreciated, thank you!