How can I start a program even before Windows starts itself?

This Sysinternals article explains the registry entry involved. But the application cannot use any of the "subsystem" APIs such as Win32 (others are the POSIX and OS/2 APIs). It must use the mostly undocumented NT "native" API. The great majority of applications developed for Windows aren't pure native API apps.

How can I start a program even before Windows?

I believe you are asking the wrong question (In which case, look at start menu > startup, or msconfig).

However, just in case you really do mean what you asked:

What kind of 'program' would you be referring to?

Are you referring to a different Operating system?
Look at GRUB/GRUB2/any other boot loader

Are you referring to a DOS application (ie some sort of old inventory/customer manager)?
Are you using win9x? That's the only situation when a DOS application would make sense insofar as 'loading before windows' is concerned.
If you're not using win9x, then you probably want to multi-boot.

Are you referring to a Windows application? (as in graphical user space application?)
The simple answer is No. (You can have it startup along with windows, just not BEFORE it.)

Are you referring to auto-starting a Windows Service/daemon/something that sits in the background?
Sure; just set it to start by default. ie if it's already defined as a service, go in control panel > administrative tools > services.
If it's not already defined you can add it.

Are you actually referring to a 'program' running before windows (ie windows xp/vista/7)?
Could you please give an example of something that would need to do that?
Other than boot loaders, disk encryption software or perhaps recovery environments (ie GRUB, truecrypt's boot loader, or any of the many flavors of recovery software).