Narrow the problem
The most likely cause is misconfiguration of mod_rewrite or clean URLs on the new server. Confirm this by short-circuiting the clean URL system and requesting pages directly, like this:
If the login page is shown, then you can assume that Drupal's page serving mechanism is working properly, but mod_rewrite isn't working. To determine if mod_rewrite is enabled, create a file called phpinfo.php in the root of your site. This file should be accessible from a web browser and contain this code:
Ensure that mod_rewrite is enabled
Navigate to phpinfo.php in a browser like this: http://www.example.com/phpinfo.php
On that page, look for a section called "Loaded Modules" and check that mod_rewrite is included. If not, mod_rewrite is not being loaded by apache and will need to be enabled. The process will be different depending on the server platform and apache build. Keep the phpinfo.php file for now - it will be helpful later.
Ensure that Drupal's .htaccess file is being used
Once it's been confirmed that mod_rewrite is enabled, double check that Drupal's .htaccess file is in the site's root, and that it is working. Confirm that .htaccess is enabled by temporarily replacing Drupal's .htaccess file. Make a backup of the existing .htaccess and create one like this...
Now try the site URL without specifing a page or file in a web browser: http://www.example.com/. If you see PHP's phpinfo dump, the .htaccess file worked and you can restore the old one. If not, the server may not be allowing .htaccess overrides for your site.
Double check your rewrite_base setting
If phpinfo was displayed, something may be misconfigured in the existing Drupal .htaccess file. Check the documentation for "RewriteBase" and "RewriteEngine" settings.
Enable necessary .htaccess overrides
If phpinfo was not displayed, locate your apache configuration file and enable the necessary .htaccess overrides. This location will vary by server platform, so check the appropriate documentation. In this example (Ubuntu server), the default apache vhost configuration was located at:
To configure mod_rewrite from .htaccess, the apache config needs to allow at minimum "FileInfo" overrides. In order to make the simple DirectoryIndex test work, apache needs to allow "Index" overrides. Locate the section in the apache configuration file or included vhost configuration file that looks like this:
Within that block, either add or edit the apache AllowOverride directive. This can create security risks, so see the official reference here:
To allow all overrides, it will look like this:
To only allow selected overrides, specify them individually like this:
AllowOverride Indexes Options FileInfo
Now reload the apache configuration. This is also different by platform, so consult the appropriate documentation. On Ubuntu server the command is:
# /etc/init.d/apache2 reload
Navigate a browser to http://www.example.com/ and PHP's phpinfo should be displayed. If so, replace it with Drupal's .htaccess file and your site should now be working as expected.
If clean URLs are still not working, go back to the section titled Double check your rewrite_base setting.