Different operating systems have different standard sizes.

Icon sizes for Windows Vista and Windows 7

It depends on your application, but here are some suggestions from the Microsoft Vista Icons Guide.

Application icons and Control Panel items
A full set should contain 16×16, 32×32, 48×48, and 256×256.

Toolbar icons
Could be in 16×16, 24×24, and 32×32. For example, Internet Explorer has a customizable setting: you may switch to large icons (24×24) or small (16×16).

Dialogs and wizards
Microsoft suggests no strict guidelines for that. You should use the closest standard size matching your needs, or even introduce your own custom size.

Icon sizes for Mac OS X

Here are the icon sizes from the Apple Human Interface Guidelines.

Applications, folders and documents should include icon resources in these sizes: 16x16, 32x32, 128x128, 512x512 pixels.

Application icons and System Preferens items

A full set should contain 16×16, 32×32, 128×128 and 512×512.

Toolbar icons
Could be in 16×16, 24×24, and 32×32. For example, Finder has a customizable setting: you may switch to large icons (24×24) or small (16×16).

Icon sizes for Linux

Here are the icon sizes from the GNOME specification. Bold denotes the primary size for this kind of icon.

Object and document	24x24, 48x48, and 96x96
Application	24x24, 48x48
Toolbar	24x24, 48x48
Menu	16x16

Icon sizes for iOS (iPhone, iPad and iPod touch)

Here are the icon sizes from the iOS Human Interface Guidelines. Offtopic: consider downloading our free icons from iPhone (that's really our project; it's not a paid link).

What icon format should I use?

It depends on the platform you develop for.

You can download our free icons to test in your application. And speaking about free icons, we've got a free monster set of icons, 1100+ at the time of last update of this article (March 2013).