How do I get pretty URLs on my website?

I would like to have Pretty URL’s on my website.

For example:
http://www.whatever.com/album.php?alph=A&artist=Alexisonfire would become
http://www.whatever.com/A/Alexisonfire

I have tried so many tutorials and can’t get this to work. I’m sure that this is done with .htaccess but I just cant get it to work. My host is http://www.nearlyfreespeech.net/

Any help would be fantastic.. Thanks..