I play the Fred: First of all, <ThePhenyxx>, was this played in person? On-line? What was the time control? Were you or your opponent in time trouble at any point?
To the moves themselves:
<1. e4 e5
2. f3 Nc6
3. Nc3 Bc5
4. Nh3 Nf6
5. Bc4 O-O
6. Nb5 a6>
The knight isn't threatening much here, so there's no need to drive it off. I think it's time for 6...d5.
<7. Nc3 Nh5>
Sorry to get repetitive, but 7...d5 should have been played.
<8. g3 Na5>
8...d5 is the move. It's a doble attack on the c4 bishop <AND> the h3 knight. By contrast, one-move threats like 8...Na5 are easily dealt with, and when the c4 bishop skips away, you've got a piece out of place. Note that your a5-knight and c5-bishop are vulnerable to a potential pawn fork.
<9. Bd5 c6
10 a3 makes b2-b4 a more potent threat. But getting the d5-bishop out of harm's way was indicated first.
11. Bb3 Qe7>
Returning to an earlier theme, we've got to unlock the c8-bishop with 11...d5. We've got to open the line for the bishop anyway, and the h3-knight hangs.
Ouch. That helps you out, doesn't it?
And you took full advantage. Well spotted.
<13. Bd2 Bxa1
14. Qxa1 Nf6>
You said you were new to chess, so allow me to introduce this concept to you: When ahead in material, trade pieces. In this position, you are ahead the equivalent of six pawns but your knight is hanging on a5. 14...Nxb3 not only gets your knight out of trouble, but it guarantees that you'll keep a big material advantage. If white refuses to take the knight back after 14...Nxb3, you'll be ahead the equivalent of nine pawns - that's like being ahead by a queen.
<15. Bxa5 Qc5
16. Bd2 d5>
Good, there it is.
<17. Qxe5 Nd7>
Oops. Both you and your opponent missed that the h3 knight hangs to the bishop.
<18. Qb2 Re8
19. Ng5 Ne5
20. f4 Nf3+
Yes, knights can move backwards.
22. Ng5 exd3+
23. Kd1 dxc2+
Well, you're still in good shape but the opponent has both his bishops. The <bishop pair> is a formidable attacking unit.
25. Nf3 Be6>
That's why 25...Bf5 would have been good for you - it forces the trade of bishops. Once the bishops are traded, he no longer has the <bishop pair>, while you have your extra pawn.
<26. Nd4 Bg4+
27. Kc1 Rad8
28. Nb3 Qf2
Hassling the rook with 29...Bf3 leaves it with no safe squares: 30 Re1 Rxe1+ 31 Bxe1 Qxe1+ 32 Bd1 Qxd1#. White can avoid the mate with 31 Bd1, but it leads to utter collapse after 31...Rxd1+ 32 Kc2 R8xd2+ 33 Nxd2 Rxd2+.
After the bishop retreated to e6, there's no longer a double attack on the e1 square by the rook and queen, so the attacked queen must retreat.
31. Bd2 g5
33. Re1 Be4
I like 34...Bxc2, but I think this position needs more analysis than the quick once over I'm giving it right now. The line I've hashed out goes:
35 Ba5 Rxe1+ 36 Kb2 (36 Bxe1 Bxb3 37 axb3) 36...Rb1+ 37 Kc2 Qf2+ 38 Kxb1 Rd1+ 39 Nc1 Qd4
<35. Rxe4 Ree7>
Well, that about wraps it up.
<36. Rxe7 Qd8
37 Qxf7+ and mate next.
Was there some notation error here? Overstep time? Because 38...Kxg7 keeps things going.
Hope this helps, and I plan to dig further the position for black's 34th move.