I'd recommend "How to Design Programs", and if you'd like and have the time, you can supplement with "Structure and Interpretation of Computer Programs" lectures.

>Also I have heard from many sources that programming is more about constructing programs and less about memorizing code, this raises my confidence a little, assuming I am imagining what coding is like correctly.

The focus of How to Design Programs is on program design and construction, and the language it uses is very simple and requires no significant syntax memorization. It's also free and there's an IDE developed for it and the language it's based off of (Racket Lisp).

SICP is a highly-recommended book, but it's also very abstract and can be difficult, but it can be nice to watch the lectures and take notes and see how the ideas are used in HtDP. This is what I've been doing myself, I just started myself a few weeks ago.

I kind of wish there was some kind of beginner's programming IRC room or something for people like us.