I started on this page. As it turns out, not that easy.
The first thing you nedd to do on your server is install LAMP (Linux, Apache, MySQL and PHP). This is how to do that. I had no issues on the LAMP-part, but if you did, please contact me, and I will add the necessary instructions.
On to the WordPress-part, this is where it might get tricky. Assuming here that you’re also starting with a clean VPS, without any config on it.
On the main page, there is a section about “Initial Server Setup” where it is explained that you need to create a new user that has root privileges. This is where my troubles started. 😛