Removing index.php from permalinks

Hey all,

I’ve had a site going now for some time, and recently a friend of mine quipped that I should rearrange the permalinks to remove the index.php reference.

Here’s how my perma’s read:

http://mywebsite/index.php/2012/08/15/sample-post/

Of course, my fear is that removal of the index.php section will result in the site crashing an all incoming links breaking.

Should I remove the index.php portion? If so, what’s the easiest and less painful way to do it?

Many thanks,
e