We get a novice edge to start, correct? Can it come from any variety (combat/leadership/basic/etc)?
Your character starts with 1-3 edges (unless you take veteran of the weird west). The variety of edges don't mean anything at character creation...it's just a method of organization.
After character creation there are 2 types of edges that are more meaningful: Background and Professional. In both cases, they're meant to indicate something more than just "I leveled up". Basically, they require GM permission, but really it just means that you should give me a heads up, so that I can work it into the story. You don't just wake up one day with the Thief edge, you need to have actually practiced the trade some and probably talked/trained with some more capable thieves. OR if you decide to become "Attractive", your character needs to have done something to make it happen, maybe cleaned up, started shaving regularly, got a new haircut, and started working out. That kind of thing. This merits mentioning now, since if you take them now, they can just be part of your backstory. Note: Arcane Backgrounds fall in this category.
How do we get Powers?
You get some when you take Arcane Background (explained below). You can also take the New Power edge to get access to another power, the Power Points edge (once per rank) to get 5 more power points, and the Rapid Recharge/Improved Rapid Recharge edges to recharge power points quicker. There are other edges available to each of the arcane backgrounds, if someone takes one, I'll fill them in on the specifics.
When you purchase an Arcane Background you get a number of powers dependent on the type. You also get a different number of power points and some sort of drawback. You didn't ask about the other 2 things, but here's the basics for Deadlands:
(I'm 90% sure this is correct)
Miracles (i.e. Blessed): have access to all powers, and don't use power points. Suffer a penalty to casting depending on rank of power being attempted (-2/rank including Novice), and suffer fatigue if they fail. Must adhere to a rigid moral code, or lose some power temporarily.
Shaman: 2 powers, 10 power points. Need to perform nightly rituals to appease the spirits. Can get away with not performing them for a bit if they follow the Old Ways Oath. Regenerate power points faster under the open sky.
Magic (Huckster): 3 powers, 10 power points. Shaken with a roll of 1 on the casting die. Regenerate Powers slowly (1/3 hours). May Deal with Devil for "free" power points, but that can also come with some drawbacks.
Mad Scientist: 1 power, 20 power points. Powers are in devices, which means each "New Power" comes with another device with its own power point pool. Devices explode with a roll of 1 on casting die causing 2d6 damage to anyone in a medium blast template (the device then needs repaired). Additionally, each time they take the New Power edge they get a random dementia.
Chi Master: 2 powers, 20 power points. Each power uses its own skill (linked to spirit).