By the rules Paladins don't need a God, but every... single... person... playing D&D picks a god for their Paladin. Being a Paladin joining the wall of the faithless is just headachingly stupid and no one plays that way.
* I know someone will come and say "I do!" Well a great big bears hug to you!
What are you talking about? Paladins don't need to choose a god to be a paladin.
I'm pretty sure they do worship a god, just like your avarage joe tending to the fields somewhere, but it can stay smething private from them not a necessity to carry out their duty.
There are a few people in the whole Realms who willingly don't worship any god because, as you mentioned, not doing it is... well, 'stupid'.