Trouble tracking down problem with Permalinks

After using WordPress on a few sites for people, I decided to install it on my own webserver (linux mint 13 running apache). I got everything installed, upgraded to 3.9.1 and started to create a basic layout. I tracked down a few minor issues with the help of google and lookinging at a working site. However, nothing I have read or tried so far has fixed the issue with permalinks. The default homepage shows up but clicking the menu link or trying to gor directly to the page gives me “Not Found
The requested URL /engraving-equipment/ was not found on this server.”

I am sure it is going to be something simple I have over looked, but I am not sure how to proceed.