I recently read the DotF section of special mounts w/leadership in detail. IDHMBWM right now, though, so I will have to recall from memory. I believe to get a dragon mount you need to be a minimum of 16th level (could be 15th) and that you also have to have the leadership feat.
DotF has a laundry list of mounts available dependent on the level of the paladin. At early levels, w/ or w/o DotF you are going to be limited to a warhorse mount. However, you should get access to dire lions, griffons, and yes, ultimately dragons, if using the
OPTIONAL rules presented in DotF.
The thing is, the more powerful the mount, the less powerful the increase. Thus, again if I remember correctly, a dragon mount gets no bonus at 16th level - rather it is treated as if you got a mount at 5th in terms of bonus HD, NA, etc. It will increase when you hit 18th, but that's it - not that that's exactly a problem

.
There are two subsections of that part of the book that I believe warrant special attention. First, it plainly states that introducing a dragon as a mount carries with it an enormous increase in power to the character relative to having a standard warhorse mount. This is due not only to the dragon's special powers which are at that point, fairly mighty, but moreover due to the dragon's nature and intelligence. Dragon's are cunning - probably moreso than their riders. Moreover, a Dragon ought not be treated like a mount but as another party member.
The second subsection has to do with retiring mounts and I think this might be the best knowledge for you right now. It discusses in detail the lifetime of mounts and what happens when they get old. Afterall, even a human paladin will long outlive his warhorses prime-life span. I don't think you have to wait as long for a new mount when you retire a mount (I could be wrong though). I do know that when you do retire a mount and finally get a new one, you can choose a more powerful base creature.
Hope that helps - I would strongly recommend picking up the DotF splatbook - it has a lot of cool info apart from all of the min/maxing stuff.