<p>I've been doing html, css and javascript for quite a long time, mostly for my very own enjoyment. I would say I know fairly much, I've created many simple games and apps and experiments with javascript. However there is only so much that is possible to do in the browser, for any more "complete" websites I am constantly confronted with my ignorance on server side programming.</p>

<p>So, what do I need. I need to get my head around how to use databases and how to use some server side programming language, I guess. What is the right choice? What should I avoid?</p>

<p>Thanks.</p>

PHP
and
MySQL
have a pretty low barrier to entry (they're both free and ubiquitous).  I'd start with those, since most hosts provide them for you.  As an added bonus, they work really well together (and PHP isn't very hard to learn coming from a web development background).
Head First SQL
is a great book for learning MySQL.  All of the examples in the book are done on MySQL.  The book even explains where to get it and how to install it.  As for PHP, the
introductory tutorial
at official website is the best place to learn it.
Update:
Head First PHP & MySQL
is now available.  I haven't read this one yet, but other books in the series and by the same author are great for learning new languages from scratch.