What you need to do is find out what Gods are available to you, and what Domains they allow you to take. Each Cleric can select 2 Domains, which grant special powers and let you cast non-Cleric spells. Strength and Travel may be good choices, if any deity offers both. A Cleric's alignment has to be one step away from their God, so if you play a Cleric of a Neutral God, you have to be Neutral Evil, Lawful Neutral, Chaotic Neutral, etc..
Serving an evil Cleric does net you the ability to command undead, though it won't be easy to use. But if you can manage it, free undead minions aren't bad. The other consideration is spells- Evil clerics can only convert spells they don't need into wounding magic, where Good clerics can convert spells into healing, which is more useful. Ideally, you want to be a Neutral if allowed and worship a Neutral or Good god to get healing magic, but if this is an all-evil game, I understand if that's not an option.
There's a nice list of possible Domains right here on Enworld:
D&D 3E/3.5 - Cleric Domain List for D&D 3.5 (JHtB)