I suggest Photoshop or GIMP . . =)

Overall I recommend GIMP. It's free, and it's great (so you only lose time if you try it and don't like it). I've GIMP, Photoshop CS4, and PaintShop Pros 6 and 9 (all legit, some crazy expensive), but of those I only use GIMP nowadays. If you just want to doodle with your mouse, pre Win7 MS Paint was great for that (Win 7 MS Paint is bad at that to me, it antialiases everything and I don't want that in my MS Paint). There are other programs too for specific stuff like if you want to make sprites or something. You can make 'em with those fancier programs too, but having a limited, specific set of functions can be really helpful, like there was this old horrible sprite painting program that had practically no tools, always zoomed in really close and all you could do was make 256 color palettes and change the color in a single pixel at a time and I loved it. It all kind of depends on what you want to do and how much you're willing to use general skullduggery to get things done.

Between Photoshop and PaintShop Pro, I recommend PaintShop Pro (since you're not trying to become a professional artist that might need to follow some set standards). It's cheaper, has enough features and at least the versions I have handled vectors a lot better than Photoshop (since they've that Illustrator program for that or something). It seems like they've changed the name to PaintShop Photo. I live in the past, maan.

/edit: ...and since I live in the past, my info on stuff might be horribly outdated. Anyway, I think GIMP is great.

Gimp has the advantage of being free. But both Painter and Photoshop have trial versions that are fully featured and last a month. Photoshop is probably the most user-friendly but you'll be paying for a lot of features you'll never use. Especially if you buy a more recent version.

Painter on the other hand you can pick up for £30. That's where I got my copy and it's legit, not an upgrade or anything like that.

So Coral Painter or PaintShop Pro? For now I will use Gimp I guess... :)
So Coral Painter is best for my purposes?

I'd suggest you do some drawing on paper first before worrying about drawing on a computer.

I don't know what Newgrounds is like, but DeviantArt is really YouTube for drawing. It's not so much a place to get critiques for your work as it is to show off your work to the world. I'm not saying the site is either good or bad (unlike certain varieties of trolls), I just wanted to point out what it is.

I love Illustrator (and Inkscape, except for its GUI system that makes it very ghetto on operating systems that aren't Linux) and vector art, but vector art is a very different workflow to regular drawing. Vector art programs act a lot more like CAD programs. So I wouldn't recommend them for someone who's just started to learn how to draw.

Try the trial version first. Follow some basic tutorials on how to use it and see if you like it. As the name suggests it's geared towards digital painting and it's what most concept artists use.

But you won't know if it's really right for you until you try it. Even at £30 it's worth being certain about it first. I bought my copy more than 18 months ago so clearly it's not an offer that's about to expire. So see what you think.

Photoshop, Paint Tool Sai and Corel Painter are all great programs. Corel Painter tries to emulate real world tools, where Paint Tool Sai is something between Painter and the more digital approach of Photoshop. I never could get into Corel Painter and only used it for line drawings so far. Each program has some advantages, but they are just tools...nothing magic.

Digital Painting can become very complex. As a beginner, choose some basic brushes that you like to work with (maybe a hard round brush with and without opacity and 2 or 3 other brushes). Still, the best way to train your eye is to draw on paper every day for 1 hour and you'll improve very fast.

I would suggest you this order:
- pen + paper + some tutorial (even this I linked)
- tablet + ANY free app (even MS Paint)
- some advanced app

Having tablet is even more important than having software. If you think (after drawing on paper) that you will like to draw, try to buy some good tablet from Wacom - at least A5, but A4 would be even better and optimal for start if you are going to draw more often.

How much good tablet costs? I have no idea which tablet is good for my purposes and you seem to know lot about this...or even tips what specific table I should buy would be useful :)

The Wacom Bamboo series are their most affordable range. The Bamboo Pen is the cheapest option available in that range and will at least provide you with the ability to draw with a pen tool rather than something more akin to a bar of soap (mouse).

As for price, it's about £50 according to Google.

Don't go for non-Wacom models. They're OEMs that have been branded by several companies. Meaning it's not something that the original equipment manufacturer wanted to put their own name on. Says a lot, that.

As Navagon said, if you are going to draw a lot and would like to feel comfortable - you need any Wacom, not any other. As for prices - they aren't low but it is a very good quality.

But do not even try to buy something below A5 of drawing surface size. I have A5 myself, it's compact but I'm mostly using it for DTP or photo editing or but when I'm going to draw something - I wish I could have bigger tablet.

Prices - just look at Wacom page and check its offer then compare prices in your shop.

I think you shouldn't go buying a tablet right off the bat. Pen and paper is probably the best way to start, and there are actually some crazy perverted people who prefer mouses to tablets (like they buy a Wacom tablet, use it for a week and then put it in a shelf never to be used again since they like using their laser mouse more). Wacom's the way to go with tablets, like Navagon and Lexor mentioned.

...but Microsoft Laser Mouse 6000 totally beats any tablet ever ;)
(the words above are those of a pervert, seek for your own truth in your heart)

Anyway, don't go piling up stuff before you even begin. Practice a single thing for a while before moving on to another, unless you figure out that the thing you're practicing is totally not for you. Of course, if digital painting/drawing is what you desire and your mouse hasn't become a part of you it's sensible, but if you just want to draw, the basic stuff like pencils and paper and a bath robe are enough (and better in the sense that you don't become completely addicted to "undo").

Yes, don't go buying bells and whistles. Commit to it first. Pencil and paper. For a while. Sucks, but... or else you're just asking to have your backloggery grow from games to random hobbies.

Quick question. When I will start drawing just pencil and paper is there anything specific I should draw? Or just random objects I see?

I think it kind of depends on what you want to draw. Drawing a variety of objects you see is good for teaching perspective and shading and shapes and whatnot (and you need those skills with every drawing task except cheap webcomics), but if you want to draw Mickey Mouses, you should try to draw Mickey Mouses. :p

As I see it, drawing skill has 2 big components: technique and knowledge. You need to draw a lot to improve the technique, and you need to either draw or otherwise study a lot of different things to improve your knowledge.

Back when Warcraft 2 was new and I was a kid, I spent ages drawing "copies" of the awesome art in the manuals. I still remember some of the "oooh" moments about the things I learned just by copying. So if there are some nice drawings you like and really don't know where to begin, copying that stuff might be as good a place to start as any. By copying I mean that you look at it, how the lines go and the proportions and whatnot, and try to draw it yourself. If you just put a paper on top of the drawing and "draw through", it'll be just about completely useless (and if you "copy paste" with a computer to practice, I'll throw a shoe at you :p ). Optimally there's some sort of thought and curiosity involved with the copying, too. Maybe stuff like "I wonder what kind of shape the original artist started with" or just "why is this like this".