Developing a colouring style around a line style

[Antioch]

Greetings;

I've been lurking around these forums for a few months, and seeing as these are the forums that sparked me wanting to develop my artwork further, I thought I'd ask here.
Even considering it's a stupidly broad question, and I'm probably even asking in the wrong section.

I've been drawing with pencils, black and white, lots of lines, up until now. This is, like, 3 years of development purely in black and white lines. I'm really trying my damndest now to somehow apply colour to it. It's too messy for me to just sort of slap some colours on a layer underneath the linework, and whenever I try to use the linework as a guideline, it ends up looking really bad. I'm asking if anyone else had a problem with using colour at first, and if anyone could share their ideas on exactly how would one go about learning to use colour as a medium, without having to relearn their artistic thinking altogether?

Thanks in advance.

Note: I can post a general idea of what my stuff looks like if needed. I think it's not all that important.

[Sinix]

Yea, show some of this stuff you want to color and you might get some specific help. Colors are tricky, and it takes alot of work to get good with them.

[Antioch]

I went and looked through my folders and found two. Please be gentle as far as critique goes; I've not had any training whatsoever, didn't even take art as a subject in high school, and it's very evident. :^^;:
I've just put links to them, seeing as they're large. Not... filesize large, just dimensionally big.

Horrible awful drawing of a robot man (http://www.kaitenkenbu.net/antioch/servant.jpg)

Horrible awful drawing of a girl with a sword (http://www.kaitenkenbu.net/antioch/swordgirl.jpg)

I chose the latter purely because it's about as messy as I get. I'd ideally know how to work from that, seeing as it would save me a lot of time in doing the initial sketches.

I chose the former because I rarely do toning and such, and would specifically like to learn how to end up with the same picture, without any visible linework at all.

Again, I'd appreciate any help anyone can give me.