I've forgotten the formal proof for this, but hopefully this is correct:
Consider a D6 (for the sake of concrete language).
When you roll a 1, you reroll the die and keep the result. This produces an average value of 3.5, and happens 1/6 of the time.
When you roll a 2, you reroll the die and keep the result (even if it's lower). This produces an average value of 3.5, and happens 1/6 of the time.
When you roll a 3, you keep the result. This produces an average value of 3, and happens 1/6 of the time.
And so on.
This gives the following formula for the average of the D6: \$ (3.5 + 3.5 + 3 + 4 + 5 + 6) / 6 = 4.1\bar{6}\$.
Working similar formulas for the other dice, we get this table:
\begin{array}{lccc}
\hline
\text{Die} & \text{(standard) Avg.} & \text{GWF Avg.} & \Delta \\
\hline
\text{d4} & 2.5 & 3.00 & 0.50 \\
\text{d6} & 3.5 & 4.1\bar{6} & 0.6\bar{6} \\
\text{d8} & 4.5 & 5.25 & 0.75 \\
\text{d10} & 5.5 & 6.30 & 0.80 \\
\text{d12} & 6.5 & 7.3\bar{3} & 0.8\bar{3} \\
\hline
\end{array}
Dice are independent. 2D6 will have an average value of \$2 \cdot 4.1\bar{6} = 8.3\bar{3}\$.
Common weapon average damage (Great Weapon Fighting):
\begin{array}{lcc}
\hline
\text{Weapon} & \text{Avg. GWF dmg} & \text{improvement w/ GWF}\\ \hline
\text{Greatsword (2d6)} & 8.3\bar{3} & 1.3\bar{3} \\
\text{Greataxe (1d12)} & 7.3\bar{3} & 0.8\bar{3} \\
\text{Longsword (1d10)} & 6.30 & 0.80 \\
\text{Double-bladed Scimitar (2d4)} & 6 & 1 \\
\text{Smite (level 1, 2d8)} & 10.50 & 1.50 \\
\qquad \text{(+ weapon damage)} \\ \hline
\end{array}
Observations:
The ability works out to about a +1 to damage.
It scales to almost a +3 when smiting. The more dice you add (high level smite, for example), the better the ability.See errata, below
The bonus is "swingy." It can range from a -2 to a +10 on 2D6, for example.
Errata
In April of 2016, Jeremy Crawford ruled that additional dice from abilities like smite can not be re-rolled by Great Weapon Fighting.
If you are using a versatile weapon, you can only gain the benefit of the Great Weapon Fighting Style if you you are using it in both hands. Similarly, you can only gain the benefit of the Dueling Fighting Style if you are using it in one hand. (And holding no other weapons.)
So, let's take a look at how this breaks down with a longsword (or battleaxe, they're equivalent.)
- 2-handed: 1d10 + Str, reroll 1s and 2s. Average damage = 6.3 + Str
- 1-handed: 1d8 + Str + 2. Average damage = 6.5 + Str.
Obligatory anydice link: http://anydice.com/program/5b1e.
As well as this, wielding your weapon 1-handed allows you to use your other hand for something. (Like a shield!) This can be a huge benefit.
So for versatile weapons, the Dueling Fighting Style is actually strictly superior to the Great Weapon Fighting Style.
However, if you want to use a two-handed weapon, you should probably use an actual two-handed weapon rather than a versatile one, at which point you can achieve much higher damage.
Best Answer
No, Paladins cannot get the Two-Weapon-Fighting Fighting Style. The list in their class description is exhaustive.
This is apparent from the feature's description (emphasis mine):
If you were supposed to choose from all fighting styles, then there would likely be a separate list in the PHB that isn't part of a class description. However, each class that has access to Fighting Styles lists its own selection of Fighting Styles - this is not a coincidence.
Fighters can choose from among all fighting styles, as fighting is literally in their name. They're designed to be viable for any kind of nonmagical combat - regardless of whether it's melee or ranged, and how you want to fight - well-armored, agile, two-handed, with a giant greataxe, etc.
Rangers, on the other hand, focus on dexterous combat, and especially ranged combat (duh). Their available Fighting Styles reflect this.
Barbarians are a dedicated melee class, but since their "theme" is rage-smashing stuff instead of elaborate fighting skills, they don't gain a Fighting Styles, but other features instead.
Paladins, lastly, are historically* chivalrous, honorable defenders of good / destroyers of evil that are usually portrayed as melee combatants that gain access to a few spells. Their Fighting Styles reflect this similar to the Ranger, except their "theme" is not about dexterous two-weapon-fighting or archery - hence they don't get access to the respective Fighting Styles.
* in 5th edition, this isn't as strict anymore - previous editions had alignment restrictions on classes and the like, but 5e is a lot more open in many ways. Instead of always being the classic lawful good idealist, Paladins can also be evil; see this question, for instance. What stayed the same is that they are supposed to adhere to a strict code of some kind, and follow its principles.
That being said, while the explanation above reflects the RAW and RAI (rules as written/intended), you can always ask your DM if he can make an exception here, allowing you to pick a different fighting style for your Paladin. Mechanically, it shouldn't be an issue.
Other than that, there are also RAW-legal ways to gain access to non-Paladin-native fighting styles as a Paladin, which mostly (or all, I'm not sure) require multiclassing, as detailed in Someone_Evil's answer