So I should make a couple running animations on Paint.net (I finished the Photoshop trial and that's all I have), then export them to that program? Wouldn't that take out the whole need of an animating program if I paint all the animations in another program? Think I misunderstood.
I'd recommend Gimp over Paint. It's still free.
You don't paint all the frames of your animation, just the key frames (so for a walk cycle, between 3 to 6 frames depending on how detailed your sprite is. You then use a program with bone behaviours like Anime Studio Pro (though there are plenty of others) to create additional frames in-between the key frames. You do this by duplicating the key frames and editing them with bones, blending the animation together.
For example, here's two key frames from my wolf:
<img src="http://i216.photobucket.com/albums/cc212/darkstorne/5_zps085231d4.png" border="0" />
<img src="http://i216.photobucket.com/albums/cc212/darkstorne/5-5_zps02806e0e.png" border="0" />
I have a total of 8 key frames like that for him. If I left it at those eight frames, it would be an incredibly poor animation - you'd easily see when one frame changes to another. So I used Anime Studio Pro to turn it into a 22 frame animation by duplication the key frames and editing the duplicated frames, tweaking leg positions, head position, tail movement etc, so that the key frames blended together better. Much faster than painting all 22 frames by hand, but you'll still need to invest a lot of time painting the key frames:
<img src="http://i216.photobucket.com/albums/cc212/darkstorne/Wolf-GIFfaster_zps4102a1a5.gif" border="0" />
Animation is not easy, and it is not fast. If you're looking to create one single image of a character and create a walking animation from that, it's not going to look anywhere near as good. It can be done though, using vector art. A lot of flash games use this animation technique. They break their image up into (using a human as an example) torso, head, left arm, right arm, left leg, right leg. And then just move the individual pieces around to create animations. It doesn't look natural though, and definitely looks cheap and rushed. It all depends on your own talents if you're an artist, or on your contracting budget if you're not.