well, there's A LOT to be learnt about logos, it's very hard to be explained in a short answer. Usually, logo designers are a league of its own, I've made hundreds, maybe thousands of logos and I consider myself just decent. On the other hand, most professional logo designers tends to be barely decent at other aspects of design.
Anyway, you need a concept, understand it and then try to incorporate that concept into a logo with as few elements as possible (yet the story has to be told, so to speak). Depending on the logo, the concept, where is it going to be used, the demographics (is it for young people? kids? women? some ethnic group? ), the media where the logo is going to be used, the printing procedures and so on and so on and so on you build a few (or a lot) mockups. You may need to decide between curvy lines, straight lines, know A LOT of psychology of color, positioning and balance. Once you have all that, you must build a color version and a black and white version. A good procedure is to see if the black and white version needs any color adjustment. If not, you've something good. It's always a good idea to build logos knowing something about color blind people (about 8/10% of population) so try not to mix green with brown, dark orange or red. Of course, it needs to be scalable without any loss, so it must be built with vectors, either using photoshop vector tools or Ilustrator/Freehand/Corel (way better for resolution).
About sizes, it all depends, but as long as they're made in vectors it doesn't matter since they'll be scalable, so for web logos something like 200% of the size that will be used is OK. For print logos, I'd recommend something like 8 to 10 inches (measured in diagonal, like PC monitors) at 300 dpi