One of my players just submitted a character sheet for a paladin who doesn't follow or worship any god. This seemed strange to me, but looking at the Player's Handbook, the only relevant line I could find was this:
Player's Handbook, page 82:
Although many paladins are devoted to gods of good, a paladin’s power comes as much from a commitment to justice itself as it does from a god.
This seems to be maddeningly vague, and doesn't really answer one way or another. The PHB seems to assume that a paladin will follow a god, but doesn't actually come out and say, "Pick a god" in the same way that it does for a cleric.