As can be seen in this question, with the relevant quote from the Players Handbook:
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.
However, while not an official ruling, this series of tweets from Ed Greenwood counter this and states that in FR, they are required to follow a deity:
One becomes a paladin by hearing and accepting a call to holy service. That acceptance is cemented by an oath. If a paladin transgresses against their oath, the usual absolution, as the PHB states, is to seek absolution from a cleric of the same faith. Paladins DO worship deities, and like any other mortal, may receive requests from mortal priests or divine servitors, or messages directly from a deity […]
[…] Although you, as a paladin, serve a god or alliance of good gods (to literally fight evil, and do so largely ‘in your own way’ […]
[…] However, if your deity commands you to do something (like obey or work with a mortal priest) and you don’t, you shouldn’t expect to retain your paladinhood. What makes you a paladin is a “sacred oath,” and therefore the support of the gods […]
Is this a valid ruling backed up with material from a sourcebook (And if so, which one), or is this just an unofficial stance/interpretation of a staff member?