You are correct that the TES IV: Oblivion leveling system is confusing and frustrating. (it's nearly the same system as in Morrowind, btw).
So if I start to level faster because I'm running around spamming spells to get skill-ups, should I stop that? How do I know I'm not leveling TOO fast?
You'll know your may be leveling too fast if your attribute bonus in important attributes are small (2 or less). If you're not getting some 3s or 4s you may be leveling too fast.
What attributes are important somewhat depends on your character. Endurance is typically important because it gives you health points.
For a melee character Strength is important, for a bow and arrow and sneaky character agility is important. For a mage willpower (assuming a non-Atronach) and intelligence is important.
You get better attribute bonuses by increase BOTH major and minor skills associated with that attribute. For example, if Blade is a major with Hand to Hand and Blunt as a minor, you get a better bonus if you in addition to your blade you also punch or bash things every once in a while. That is somewhat counter-intuitive. Also counter-intuitive is that it is bad to put all skills of a single attribute as majors.
One other thing about leveling, it is good to focus on one kill skill rather than leveling several evenly. For example it might be best to focus on a skill like Blade (just as an example) rather than evenly increase Blade, Marksmanship, and Destruction.
It's a great game, but the leveling system stinks. Hopefully it will improve in Skyrim.
One last thing. If you're on the PC I recommend getting a mod that changes the leveling system. In particular I recommend: http://tesnexus.com/downloads/file.php?id=14065
with that mod much of what I said above it not applicable, and leveling is smooth, natural, and intuitive.
I also recommend the OOO overhaul mod (it's huge) which makes many gameplay changes but in particular it reduces level scaling to something much more reasonable (though it can make gameplay harder, particularly for lower level characters)