First off, you'll need Photoshop or Paint Shop Pro to get started. This isn't something you can effectively do in Microsoft Paint, and don't even try.
Secondly, you must have a good idea of what theme you're trying to achieve, and perhaps look through websites that already offer free layouts to inspire you. I searched Google and found
http://www.hot-lyts.com/ to be a good resource.
Third, learn the basics of Photoshop and acquire the information about layers and banner-making. Look through whatever tutorials you can find over the internet. You might want to look through some of CreateBlog's stuff or
http://www.tutorialized.com/tutorials/Photoshop/1, and search specifics such as effects, making banners, layers, textures, text, etc.