This website has good instructions! Here they are for Ubuntu, augmented with some small modifications:

1.  Install a LAMP stack on your server (apache, mysql, php)
2. Download the latest wordpress (say into your home directory)

   wget http://wordpress.org/latest.tar.gz
   tar -xvzf latest.tar.gz
   cp wordpress/wp-config-sample.php wordpress/wp-config.php
   

3. Create a database and configure it

   mysql -u root -p #to start mysql
   CREATE DATABASE DatabaseName;
   CREATE USER User@localhost;
   SET PASSWORD FOR User@localhost= PASSWORD("ThePassword");//choose a different password!
   GRANT ALL PRIVILEGES ON DatabaseName.* TO User@localhost IDENTIFIED BY 'ThePassword';
   FLUSH PRIVILEGES;
   exit;
   

4. Create the directories for the website<

   sudo mkdir /var/www/website #where website is, e.g. ryanmartinphd.com
   sudo cp -r wordpress/* /var/www/website/.
   cd /var/www
   sudo chown www-data:www-data * -R #www-data owns the direcctory
   sudo usermod -a -G www-data linux_user_name #not strictly necessary
   sudo vi /var/www/website/wp-config.php #edit this to set the database parameters (next step)
   

5. Configure wordpress for the database.In the wp-config.php file, make sure to edit these to the same value you did when setting up the database in mysql:

   define('DB_NAME', 'DatabaseName');
   define('DB_USER', 'User');
   define('DB_PASSWORD', 'ThePassword');
   

6. Configure a virtual host on apache. Start with the default virtual server:

   cd /etc/apache2/sites-available
   sudo cp default website
   sudo vi website
   

   Now edit the following lines:

   <VirtualHost *:80>
   	ServerAdmin your_email_address
   	ServerName website.com
   	ServerAlias www.website.com
   	
   	DocumentRoot /var/www/website
   	<Directory />
   		Options FollowSymLinks
   		AllowOverride None
   	</Directory>
   	<Directory /var/www/website>
   		Options Indexes FollowSymLinks MultiViews
   		AllowOverride All
   		Order allow,deny
   		allow from all
   	</Directory>

   Now, enable the site, install an additional php module, enable mod_rewrite, and restart apache:

   sudo a2ensite website
   sudo apt-get install php5-gd
   sudo a2enmod rewrite
   sude service apache2 restart
   

7. Launch the wordpress site by navigating to it. This will let you create the first user and should automatically setup everything
8. Edit /etc/php5/apache2/php.ini to change the max_post_size, and max_upload variables to something bigger than their defaults (e.g. 100M).