First thing you should check if you get Not Found error is that you have the .htaccess file on your site's root. Note the dot in the beginning!
If you have the file check its content, try replacing it with htaccess.txt included in Joomla package.
If correct .htaccess file is in place then your .htaccess override doesn't work or mod_rewrite module is not activated. Make sure mod_rewrite module is loaded and your server configurations allow .htaccess override.