Here’s an interesting list of typefaces available per platform.
It shows, for example, that Lucida Grande is available on 100% of all Mac OS systems, as is Helvetica.
It shows also that Times New Roman is less available than some might assume. It’s on 99.37% of Windows, 94.25% of Mac OS, and only 64.76% of Linux systems (look for each occurrence separately by platform).
Unfortunately, the site cannot show a total frequency for all platforms.
As @richardhenry demonstrates, providing a graceful cascade in your CSS in important if you value typeface in your web pages. Make sure you employ a generic font (i.e. serif, sans-serif, monospace, cursive or fantasy) as the catchall in case none of your favorites are available.