I had to search various sites to solve this problem so I figured I would pass on the knowledge in one succinct solution.
How to get WordPress permalinks / pretty links to work in Ubuntu 10.10 with Apache2:
By the way, this should be the same in Ubuntu 10.04 as well, but I haven't actually tested it there as well.
1. Manually create a ".htaccess" file and save it in your main WordPress directory. (This is the one with the wp-admin, wp-includes, and wp-content folders.)
2. Go to the Ubuntu terminal and type:
sudo chown -v :www-data "/enterYourFilePathHere/.htaccess"
You should see a line printed saying that the (group) file ownership has been changed to www-data (Apache2).
3. Give Apache2 write access to the file:
sudo chmod -v 664 "/enterYourFilePathHere/.htaccess"
You should see a line printed saying that the mode of the file has been retained.
4. Next, we have to allow WordPress to write to the .htaccess file by enabling mod_write in the Apache2 server. Type the following in the terminal:
sudo a2enmod rewrite
You should see a line printed saying that it is enabling mod rewrite and reminding you to restart the web server
5. So let's do that. Restart the web server, Apache2, for the changes to take effect by typing:
sudo /etc/init.d/apache2 restart
We are all done with the command line prompt; you can close the command line window now.
5. Go into your WordPress admin panel (i.e. http://yourDomain/wp-admin). Go to the Settings --> Permalinks and select the permalink format of your choice. Hit the "Save Changes" button.
6. DONE! Go to your site and check any page (other than your homepage) to ascertain that everything is working as expected.
Hope this helps someone. Leave me a comment below.