Shugenja IRL were ascetic Monks who existed in Japan between the 7th and 14th centuries.
They were the Japanese equivalent of Shaolin warrior monks; who spent most of their days in contemplation and learning but also trained their bodies to perform spectacular feats of endurance and martial prowess.
This quest for physical perfection was what made them appear supernatural to the common man, whilst their knowledge of various topics such as philosophy and medicine gave them the legendary reputations as "wise men" and made them highly desirable advisors to daimyos, taking the equivalent roles as court "wizards" in Japanese culture.
3rd Edition D&D
Legend of the Five Rings (and by extension, Wizards of the Coast) took the supernatural approach to creating the Shugenja class, mostly driven by the pre-existing storyline of the Rokugan campaign setting, but because the closest realistic analogue (the Monk) was already a character class and they wanted to differentiate between the two, and so their amazing physical training has been mostly ignored.
It was originally printed in Oriental Adventures to fill the gap of Wizard which generally gets dropped for not being "oriental enough". It was then reprinted again in the Rokugan Campaign Setting and finally reprinted in D&D 3.5 Complete Divine.
The character class is best described as a divine mirror of the Sorcerer class in that they may cast spells spontaneously and only learn a few new spells each level, however unlike Sorcerers who just happen to know all their spells can cast them when they feel like, Shugenja have a spellbook-equivalent "Ofuda" that they must read from in order to cast their spells. Losing this item does seem like an easy way to cripple the class, but it's easier to consider it a divine focus which would have been necessary for most divine spells anyway.
There are no armour proficiencies, which would normally be horrifying for a divine caster and you only learn simple weapon proficiencies. Though in Rokugan this is explained as an essential requirement, since learning to wear weapons/armour is not socially acceptable for Shugenja, unfortunately this rule was just carried over to Complete Divine and you have to live with it.
Also, at character creation they have to choose both an element and a school/order, which can be simply described as a cleric domain. Unfortunately this hobbles the class even more, as being forced to choose spells from one element then restricts you from learning any spells from its opposing element, meaning your role becomes much more focussed. Following on from choosing an element, the School you choose gives you a "domain" of spells from 1-9 that you could not otherwise get in your core list, but no additional domain ability.
- Depending on your setting, your element dictates which schools you can join, where if you were playing within the Rokugan setting, your character's samurai clan dictates this and so you don't even get that choice.
Finally, they also get the ability to "Sense Elements" which allows them to roll to check for the presence of one of the four elements within range, or its particular substance (such as what types of mineral for "Earth"), while this sounds almost useless, a clever player can come up with neat uses such as a means of navigation or sensing the presence of hidden creatures (the water inside human bodies perhaps?)
The upside to all these restricting factors is the spell-list itself. Although they are divine casters, many of the spells on the Shugenja spell-list come from Arcane classes. Take for instance an Earth specialised Shugenja: his primary abilities are buffs from the earth element but since he has not restricted himself from the Fire element he can fling around fireballs and do some actual damage, and since he has also not restricted himself from the Water element he can heal his allies too.
This utility within the list itself gives the Shugenja the ability to fill the role of different casters within the group and is actually ideal for very small groups where he might be the only caster OR as a backup utility caster where other casters might be more specialised.
Shugenja aren't listed on the original post for the Tier System. They are generally agreed to be a tier 3 or low tier 2 class since, while they are a full caster, their spell list is very limited and lacks anyway to break the game. They're definitely tier 2 with Rokugan d20 material, since the additions make their spell list is far more versatile.
Making it Work
First, it has to be mentioned that if you are playing in the Rokugan campaign setting, Shugenjas are extremely limited in their multi-class choices by their clan and the impositions written in the rules that prevent them from returning to their class if they ever leave it. (outside of certain circumstances) The options in Rokugan are more designed towards careful roleplaying rather than class optimisation.
So in the core ruleset, Shugenja's are practically begging to be multi-classed since they have no scaling class features other than their Sense Elements ability which can be very comfortably dropped without any regret at all. Any divine spellcasting prestige class with ANY class features at all is already an improvement over being a Shugenja, so the question becomes what synergises particularly well? It must be remembered that half of their spells must still be of their chosen element regardless of what future prestige class they gain, also remember that as a spontaneous divine caster, gaining domains does not instantly grant you additional spells known, only broader choices of spells available when you learn more by levelling up.
The Elemental Savant is the most obvious prestige class, even suggested by Complete Arcane as a good choice for a Shugenja: It gives you very fluffy elemental resistances, spell penetration bonuses, spell DCs and eventually transforms your character into an Elemental of their chosen type. So it synergises very well with your original selection. What to be careful of though is that it forces you to change the energy type of all damage dealing spells into that of your chosen element (air = electricity, earth = acid, fire (duh), water = cold) even if these spells were granted to you from a different element... which can leave you next to useless against opponents resistant to you, so have a think about your GM's Meta before deciding if you want to commit.
Air or Fire Shugenjas can qualify for the Stormcaster prestige class from Stormwrack as early as level 7 with good choice of spells. (Water and Earth Shugenjas fail to qualify since they cannot learn the correct spells due to being locked out of opposing elements.) Being a Stormcaster gives you a class feature at every level, ranging from enhanced electricity damage, crazy resistances, to weather control. This class only hampers your spellcasting progression by one level, but even then it still enhances your caster level for your chosen element by +2 giving you a net gain of +1 at a cost of only one less 9th level spell known and per day (5 from 6).
The Earth Dreamer is a five level prestige class from Races of Stone that is qualified for very easily. It gives you a set of earth-based class features including Tremorsense, Divination and the ability to see and move through stone as if it was not there. The best bit about it though is that it does not require you to be an Earth Shugenja, only needing the Earth Sense feat and a few skill points for entry. So a Shugenja can use this class as a filler until he qualifies for another prestige class and mix up his elements like something out of Avatar.
The Hexer prestige class from Masters of the Wild is relatively easy to qualify for, indeed Shugenja is the main way to qualify outside of Adept. Requiring lightning bolt as a divine spell (done) and ranks in Knowledge Arcana, Spellcraft (which you get as class skills) and
Wilderness Lore Survival (The apprentice feat in DMG2 and other prestige classes can get you this), as well as being a "primitive" (is being behind the sakoku primitive?). In return for these modest requirements you get full BAB (helps land touch spells better, though still D6 HD so no entering melee) a hex ability that scales off wisdom (your dump stat) a few times a day, and, most importantly, the ability to add wizard spells to your spell list (you still need them as spells known though). These spells can be of the maximum spell level you can cast, and with a typical entry (8th level Shugenja casting) you're in a position to grab the spell on your next level up.