Start menu/screen opens either by clicking the Start button, pressing Windows Key or using keyboard shortcut Ctrl+Esc.
Windows XP has a somewhat old-style Start menu (that some people like very much) - you have to open the All Programs list and then scroll through it to find and launch a program.
In Windows Vista and Windows 7, just type in a few letter of that program's name to Start menu Search box. For example, if you want to open Microsoft Security Essentials, type in "security" and click the program name.
In Windows 8, Start screen has the new Modern UI/Metro look with tiles of different size and color. Because it fills the whole screen, it is now called Start screen. To search for a program, just start typing a part of its name - for example, to find Windows Defender (the free built-in protection from viruses and malware, comparable to Microsoft Security Essentials), type "defender" and click the result. All searches are performed in Search pane.

Start menu Search box in Windows Vista and 7 also searches from Control Panel, your documents and libraries and e-mails. No need to open Control Panel and start looking for something in the maze of options!
The same Search box works also like Run command in previous Windowses did - so to run cmd.exe (Command Prompt), type it in and press Enter key on your keyboard.
In Windows 8, there are different searches available - keyboard shortcut WINDOWS KEY+Q opens Search pane and looks for apps, WINDOWS KEY+W opens Search pane and looks for settings, and WINDOWS KEY+F opens Search pane and looks for files. You can also switch between result types using the Charms bar on the right side.
With User Account Control in Windows Vista, 7 and 8, you sometimes need to launch programs with administrative rights (elevated privileges). To do that, right-click on the program name and select Run as administrator. You can also run a program as an administrator by stopping your mouse pointer on the program name (or navigating with arrow keys) and using keyboard shortcut Ctrl+Shift+Enter.
In Windows 8, right-click the program and then click Run as administrator in the App bar displayed below. Alternatively, hold down Ctrl and Shift keys while clicking the app.

You might also want to read the Windows Desktop, Start menu and folders article for an overview of Start menu.
Because Start menu options are so different in each version of Windows, the actual customization part has been divided into separate articles: