Welcome to the Linux community.
Not every computer comes with Windows preloaded. While it is true most notebooks do there are a few companies out there that offer preinstalled Linux systems, maybe worth looking into.
http://linuxpreloaded.com/ lists some companies that sell preinstalled Linux systems.
Choosing a notebook to work with Linux can be hard. Some hardware is quite difficult to get working while some works out of the box with ease. I have found most Intel based systems to work fairly well. Nvidia graphics to be easy to get working if not somewhat less polished and AMD to be either work great or to not output video correctly at all.
One option might be to get a bootable Linux DVD or USB drive and live boot a laptop on display in a store, if the sales people are okay with it, that will let you see if the hardware is supported and give you a general idea on how it will run.
Finally, if you do get a computer that comes with Windows, before doing anything create the restore CDs/DVDs if it doesn't come with any. This way you can restore the system to factory if something goes wrong (or if you need to return the system due to incompatibility with Linux). Next install Linux, this can be done side by side with Windows (normally it will shrink the Windows partitions) or just wipe out Windows all together.
Linux can be really frustrating at first but once you get used to it Linux (POSIX systems in general) can be very powerful and rewarding to work with, I hope you have fun.