That's the premise for the movie anyway. As far as the game is concerned, you have a fairly basic platformer that uses WALL-E's unique form for some interesting puzzles. From what I was able to play, WALL-E will have to do everything from throw cubes of trash at various switches to cause pathways to fall into place, power up machinery and (eventually) work with his cold, sterile love interest in order to progress through the levels and complete the game and movie's eco-friendly message.
WALL-E himself has a few interesting features that makes him appear a little different from most platformer characters. For instance, he has a "box form" where he tucks in all of his extremities when scared. This occurs quite frankly, like when you end up on a switch that causes a massive hammer to swing down and knock you across the area, or when you end up on a steep hill and need to slide down. You can also enter this mode at will and roll about the level. Also, since he is essentially a mobile trash-compactor, WALL-E frequently goes up to piles of trash, scoops them up and pops out a cube that he holds on his head. He can hold up to three, and different cubes have different properties.