All pokemon move differently, although some do things I wouldn't expect.
Like Pidgey just walks behind you, although Pidgeotto is always flying, while as another poster said, water pokemon that live in water because they have to magically float or slide along, like the Red Gyrados just slides along with you.
Still, the pokemon I've seen walking with me so far look quite cool, I've only seen a few so far.
Credit to .Impact for the sig & avy