Hi,
In your admin, go to Settings > permalinks and revert to the 'default'/ugly setting, then check the links on your site to see if they are working.
If they are, go back to the permalinks section and reselect the permalink structure you want to use. If those links are now broken, the problem lies in your.htaccess file.
There should be a .htaccess file in your root, along with the index.php file, wp-content, wp-admin folders. If you can see these other files & folders, you're in the right place
If there isn't a .htaccess file there, create a file called 1.htaccess using a text editor, copy & paste the code below into it, upload it to your root via an ftp client, then check the file to make sure no wierd characters have been added. If it looks fine, rename it to .htaccess.
# BEGIN WordPress
<IfModule mod_rewrite.c>
RewriteEngine On
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule .* index.php [L]
</IfModule>
# END WordPress
http://codex.wordpress.org/Using_Permalinks#Using_.22Pretty.22_permalinks
Favicon: http://wordpress.org/extend/plugins/personal-favicon/installation/
If you can't get that to work, try a different plugin and follow its installtion guide.
Re NavBar Icons: check out http://keremerkan.net/posts/adding-facebook-and-linkedin-icons-on-mystique-v2-x/