They're eerily similar. They both have some exploration and platforming. The battle systems are similar and require timing in both series (there's less focus on dodging attacks in Paper Mario, though). They both have a lot of humor. Other than the graphics, the differences are slight.
The badge system is better/more developed in Paper Mario, and obviously you only control Mario outside battles. The Paper Mario games tend to be split into chapters with a new area per chapter and don't have the same sort of Zelda-esque overworld as Superstar Saga and Bowser's Inside Story, though you're allowed to go back and search for anything you may have missed.
If you like one series, you'll probably like the other (Partners in Time and Super Paper Mario excluded).