Prestige Classes are just like any other Classes, except where specific rule says something else.
From OGL content*:
Prestige classes offer a new form of multiclassing. Unlike the basic classes, characters must meet Requirements before they can take their first level of a prestige class. The rules for level advancement apply to this system, meaning the first step of advancement is always choosing a class. If a character does not meet the Requirements for a prestige class before that first step, that character cannot take the first level of that prestige class. Taking a prestige class does not incur the experience point penalties normally associated with multiclassing.
Emphasis mine. So if Paladin takes a levels if PrC, he is multiclassing all right.
Now, your player is wrong. Paladin can take any PrC he meets requirements for. The only issue is - he cannot ever take a level of Paladin again, unless PrC says he can. If prestige class has a rule that says that character can get levels of Paladin later, then she can, because specific beats general.
Example of such class (courtesy of Charlie) is Knight of the Chalice (Complete Warrior, p. 53):
Multiclass Note: A paladin who becomes a knight of the Chalice may continue advancing as a paladin.
So this class is an explicit exception. Some classes in Defenders of the Faith are exceptions, too. Probably few more scattered across sourcebooks. And that's all to it.
* Note that part about no XP penalty never made it to 3.5 DMG. It was in 3.5 OGL SRD, in 3.0 DMG and in 3.5 Complete Warrior. And 3.5 FAQ but, surprisingly, not errata. And bit different wording in each place. In this answer, I took wording from SRD, because that's where OP got Paladin class from, so this makes most sense to me.
Paladins are not Druids
The Oath of the Ancients has nothing to do with nature; it is about life and light.
A Green Knight has committed to fighting for a world where things can live and grow and flourish. Here, "things" includes plants and animals, true, but also includes people and ideas and art and concepts and societies.
Green Knights use growing things as their symbols because those things are the opposite of death and decay, which symbolise what the Knight is fighting against.
They do not necessarily have to kill wicked people and monsters. A Green Knight's focus is providing an environment where the light can prosper. If that can be done without killing (perhaps by moving the creatures on), then that is OK (though individual Paladins may differ on the level of restraint they feel is acceptable). If the evil creatures can be redeemed and brought over to the side of the light, that is (in my opinion) the best outcome. (Hat-tip Molot.)
Examples
Travel with evil aligned characters without any attempt at reforming them?
No. Green Knights are supposed to stand against wickedness, not stand beside it.
If there is a greater evil, the Knight might put up with a lesser evil, but only temporarily. Even so, the Knight should at all times try to redeem the wicked, through the example of their own actions (Be the Light).
Forego forgiveness in favor of killing someone who betrayed him?
Maybe - there should always be a hope of redemption. However, a strict Knight might feel that one transgression is one too many. Any Knight might refuse forgiveness to one who has betrayed them several times.
Overlook the evil and wrongdoings of man? (or any sentient race)
No. Again, the Knight is supposed to stand against wickedness, not stand aside.
They are not, however, stupid. They won't engage in pointless attacks. Throwing your life away for nothing violates the tenet of Preserve Your Own Light.
Inflict injury on someone for lying to him?
Maybe. A very strict Knight might be justified in punishing lying with injury.
Media Figures
I think Wonder Woman is an example of a Green Knight.
From an interview with Patty Jenkins, the director:
Jenkins goes on to describe Wonder Woman’s worldview as, “I believe in the betterment of you, and I believe in you, and I believe in truth. And I believe that you all can be better, and I will fight to protect you. But I also believe in better than that.”
Best Answer
Since you're asking for story research purposes, I'll answer primarily with that framework in mind. (Some of the D&D technical detail will be skipped in favour of plot-relevant information.)
So, the most important part of the answer first:
It depends hugely on who's running the game.
D&D, like most roleplaying games, is run by a game master ("Dungeon Master" in D&D-speak), who is responsible for the world. When it comes to paladin atonement, what is possible is almost entirely up to the DM, according to the DM's sense of the drama of his world. So the answers to your questions depends a great deal on what the character running the campaign would let him get away with.
With that in mind, some typical answers to consider:
A paladin who broke his paladin code on purpose - without actually doing something outright evil - could atone; that's what 'atonement' means.
By the strict rules, a paladin who willingly does something evil can't. (The D&D 3rd edition rulebook read "a paladin... loses all special class abilities if she ever willingly commits an act of evil". Free will matters; if you didn't choose to do it, you didn't break the code. That said, some GMs would have you 'fall' for any evil act, depending on the circumstances.)
Atonement is usually accomplished with the atonement spell, which is a large holy ritual and requires a pretty powerful priest to cast. How much work it is to atone is entirely a dramatic decision made by the DM. (Usually. If the party is high-level, a priest in the party might be able to perform the ritual themselves.)
In D&D 3rd edition atonement reads "A paladin who willingly and deliberately commits an evil act can never regain her paladin-hood"; the purpose of the rite is to give power back to paladins who've broken their code in non-evil ways, or who have done something evil involuntarily or by accident.
That said, this is the kind of thing a DM is very likely to house-rule differently to suit the dramatic purposes of her campaign. Personally, I love fall-and-redemption stories and would definitely ignore that limitation for a reasonably well-motivated character arc.
If the paladin isn't actually sorry, atonement won't work. (A god isn't easy to fool!)
Typically the priest would set some task to accomplish before being willing to perform the atonement, but they don't actually have to - it's just standard practice, to make sure that the paladin really means it.
Example paladin atonement quests: Recover a lost holy artifact. Defend a church under threat. Solve a tricky diplomatic or ethical problem. Make a pilgrimage to a holy site.
Typically the priest would choose something related to the original offence. If the paladin fell by willingly consorting with thieves, for example, he might be tasked to recover a stolen item of great value, or to find a way to recompense their victims.
A paladin who 'falls' doesn't actually lose any character levels; they're still the same basic character. However, all of their paladin powers stop working until they've atoned. (This includes losing their ride; paladins normally ride a magical mount sent by their god - such as an unusually powerful, smart, empathic warhorse. Or weirder things.)
This is a big deal. In D&D a paladin is essentially a Fighter who gives up some of the standard martial abilities of characters in exchange for holy power, smiting evil, divinely granted healing and a whole bunch of other useful special abilities.
So a paladin who's lost those special powers is essentially a really inferior version of the fighter.
Because of this, a paladin who atones normally regains their full prior powers - they never actually lost their level, they just lost access to their special powers. Once their god forgives them, they're good to go.
However, a fallen paladin can't gain new paladin levels until they atone, so if it takes a long time to atone everyone else in the group may be ahead when he finishes. (Also, you can't pick up some fighter levels or similar in the mean time and then go back to being a paladin later.)
Not only can a Paladin go evil on purpose, there's a character class ('Blackguard') that you usually get that way. Essentially, by pledging to a god of evil, the fallen paladin swaps all his Paladin levels for levels in 'demonic ex-paladin'.
This can rather burn your bridges with former friends. Becoming a Blackguard pretty much signals that you don't ever intend to atone.
Just because Andrew's gone evil doesn't mean his D&D character would. Partly because D&D characters can be unlike their players, and partly because Andrew would have to consciously know that he's being evil and choose to have his character follow suit - which he might not.
(That said, Andrew being the kind of person he is, I can easily imagine him having his paladin fall before he managed to do anything really evil in person.)
Also relevant for writing D&D in fanfic:
Edition
D&D depends greatly on which version you're playing. Andrew would almost certainly be playing some version of "Advanced Dungeons & Dragons", but it could be:
1st edition: The original, still used by a hardcore of "old school" players who enjoy the lethality and dungeon-crawling emphasis of early RPG design, and don't mind its quirks. Had almost no clear guidelines on paladin fall and rise, save that a paladin lost his special powers on falling, so the rest would be entirely up to the GM.
2nd edition: Basically 1st with some rules and art tidyup. Very unlikely.
3rd edition: The baseline of D&D play in recent years, and a likely choice. I've assumed this as a default for my answers. (Andrew doesn't strike me as a hang-on-to-the-old-school-regardless player, although Warren might be.)
4th edition: Didn't exist during Buffy air time, so only possible if you're set after series 7. Much more miniature/map play oriented. Not advised for your purposes anyway, since 'paladin fall' as a concept doesn't work the same way.
It's not likely you need to mention explicitly on the page, but just so you know that your answers are consistent with some version!