Depends on what you mean with "holy". Yes, rules-wise there are lots of options, both paladin and cleric were intended as holy warriors from the beginning. Deciding between both of them is simply choosing between might and miracle. Clerics usually leave you more options for deciding your way, while paladins usually are the chosen knights on white chargers... You don't have to play them that way, but some classes just evoke a certain style more than others.
Your racial background has a huge influence on your gameplay, too. Usually humans exhibit the most zeal when it comes to fighting for their beliefs, comes with the short lifespan. Dwarves are a close second, but more prone to protect thant to convert or crusade. Gnomes and halflings are a little bit too relaxed for similar zealous pursuits, and the chaotic and long-lived nature of elves leads to a different kind of religious activity, although the follower of Corellon Larethian shouldn't be discounted, especially if you want to follow the fighter/mage/cleric route...
Aasimars are quite nice. Technically, they're born to be holy warriors -- which is both boon and bane. If your path is clear and predetermined, things are a little too easy. Without doubt there's no belief.
Personally, I find it most interesting when you have to strive for "holiness", with temptation and sin all around you. That's more the western background of martyrdom, saints and salvation speaking, but then, that's the foundation for the usual D&D holy warrior anyway.
And don't forget the power of symbols and icons. It never hurts to follow cliches. Dress in white, ride a big horse, have a holy symbol on your shield etc.
I hope I didn't miss the point completely, as this is only a small subset of the clerical class in D&D. Most paladins don't differ that much from the archetypical holy warrior, but a cleric of the god of thieves or knowledge strays from this path quite a lot.
Rules-wise: Don't front-load. Starting with all those vows seems interesting, but grant yourself a few levels where you are allowed to exhibit some doubts and occasionally give in to temptation, then strive for some kind of epiphany that sets you on a straight path to heaven. Talking with your DM helps here
