I started very first idea scribbling on paper.
Later, since I felt insecure with drawing lines etc. on paper in an artistic way (though some of my best things started as a sketch during (boring) classes when I still went to school ;-) ) I used the computer. Sometimes I scanned my ideas but normally I started from scratch.
There I had no real limitations of a paper, just memory, CPU/GPU power and program will limit you. I started each of the 3 main parts for each character separately. The basics I first did in Libreoffice Draw using mouse and a tablet+pen. Then I exported as SVG and went to inkscape and did most stuff there (mouse and tablet+pen again). Sometimes I add very few things in GIMP but most of my stuff is vectors.
Then I add all into one picture and notice that the quadratic space doesn't fit all my ideas.
I mean 2500x2500 is one thing, and vectors can be scaled up and down, left and right and rotated and whatsnot without any loss. But still the quadratic area ... I would probably be better of with the A4/A3 paper size I am used to. (for what is A4 see
http://en.wikipedia.org/wiki/File:A_size_illustration2_with_letter_and_legal.svg )
Anyway, sooner or later I manage to cramp all stuff in and then I export the SVG as PNG and clip if necessary, then I make sure the sides are A x A and then I render down to 2500x2500 (the export can be rather huge sometimes, but you don't have to, I just like to have it large, then apply last things and then render down with an algorithm which preserves most info).
Then I check if I really like it and send it off asking for suggestions. (Also I sent intermediate work, which is only in parts)
This was the first time I really did artwork on the computer (ok, let aside some of my Pen & Paper RPG scribblings and stuff) and also the first time I used a tablet.
Well, I must say the tablet feels much better in a pixel/bitmap painting program, with the vectors it really depends on settings but sometimes I see every little twitch in my hand in the line. But then I was lacking training in programs like GIMP or PS. And I wanted vectors since you can correct them more easily. And you have layers all the time, every vector object is a layer of its own.
Now back to work with drawing. I'm already actually satisfied with the portrait. I'm really surprised about this.