Yeah, to cast magic in Dark Souls, you need to rock a proscribed wand for the proscribed branch of magic. For sorcery, you need a catalyst. For pyromancy, you need a flame. For miracles, you need a talisman. All of these things are clearly labeled what they are, so that is easy; no wondering if a stick is a wand or just a stick. Easy too is getting a spell, which you need to equip at a bonfire into an attunement slot; simply find one in your adventures or buy one from an NPC merchant. Did I mention attunement? To have an attunement slot into which to shove a spell, you need at least an Attunement attribute of 10, which nabs you one slot.

I skim people's posts unless it is really interesting, sorry. You can buy a Catalyst from Rickert of Vinheim in New Londo Ruins (from Firelink Shrine, take the elevator beneath the Firekeeper, in this first area find the stairway overlooking the flooded/unflooded ruins, and find his window) or from Griggs of Vinheim at Firelink Shrine (you need to rescue him first, and you will later find him at the Shrine, nearby the stairs to the Undead Burg). Both of these guys sell spells too, so you will be set. Damage from Sorcery scales with Intelligence.

Pyromancy Flames allow one to cast Pyromancy spells. You can get a Flame and Pyromancy spells from Laurentius of the Great Swamp once you rescue him (once rescued, you can find him at Firelink Shrine on the landing above the bonfire). Damage from pyromancy scales with your Pyromancy Flame as you upgrade it.

Miracles scale with Faith, and if you have ever explored Firelink Shrine, you have surely met Petrus of Thorolund. Join his covenant, and he will sell you Talismans and Miracles.

In regards to the Stone Knights, melee has always work for me. Double-hand your weapon and get behind the Knight before he stands up. R2 that tit until you can no more. If the Knight is still alive, R1 if that will get you the kill. The good (and bad) thing about this guy is the sorcery he casts. Tranquil Walk of Peace might destroy your mobility, and the Stone Knight may proceed to violate you with his greatsword, but when he casts it, which he almost always wants to do, you can still beat the everlasting crap out of him. Two added tidbits of advice: 1) Go back to Andrei of Astora and upgrade your weapon. A +5 weapon is so insanely better than its base version and takes only a little dedication to get. 2) Take Darkroot Garden slow. Case the area and clear out any enemies that might make the fight with a Stone Knight harder. See the telltale sign of an Ent? Shoot that bastard from afar and make it come to you. The glade previous to the Butterfly has a spot where two (!) Knights rest by each other, alongside four Ents. Shoot and murder the ents one-by-one, before taking a careful walk that will trigger one Knight to rise before the other, so you can still melee one before you even have to worry about the other.

Edit: Nooooooo, I spent too much time writing about the stone knights. Curse you, Flambard D'Quinceteth, and your timely replies.