1. Устанавливаем apache:
sudo apt-get install apache2 libapache2-mod-auth-mysql

2. Устанавливаем php:
sudo apt-get install php5-common php5 libapache2-mod-php5 php5-cli php5-cgi php5-mysql

3 . Далее установим mysql.

apt-get install mysql-server mysql-client

В процессе установки пакета потребуется придумать и ввести пароль для mysql:

4. Ставим phpmyadmin.
sudo apt-get install phpmyadmin

5. Ну и наконец установим java:

apt-get install sun-java5-jre

Заливаем БОТ на наш VDS с помощью WinSCP .

Наконец все программы установлены, займемся настройкой системы. Для начала создадим нового пользователя, от имени которого будет запускаться бот. Делается это командой adduser:

Теперь займемся настройкой mysql. Для начала определим кодировку базы utf8, для этого в файле "/etc/mysql/my.cnf" добавим строчку:
default-character-set = utf8

Я добавил эту строчку в следующие секции (аналогично настройкам своего сервера на firstvds):
[client]
[mysqldump]
[mysql]
[mysqld]

Сравнивая файлы настроек на двух своих серверах я заметил так же разницу в настройках памяти. Следующие строчки я изменил аналогично конфигу firstvds:
[isamchk]
key_buffer = 8
[mysqld]
key_buffer = 16K
max_allowed_packet = 1M
thread_stack = 64K
table_cache = 4

Возможно еще что-то можно уменьшить без ущерба производительности бота, но пока экспериментировать я не стал.

После изменения конфигов необходимо перезапустить mysql командой:
/etc/init.d/mysql restart

Далее настроим кодировку консоли. В этом я не большой специалист, может быть можно все сделать гораздо проще, но я сделал следующим образом:

Установим пакет locales:
apt-get install locales

Или если он уже установлен запустим его конфигуратор:
dpkg-reconfigure locales

В появившемся текстовом интерфейсе я выбрал 2 локали: en_US.utf8 и ru_RU.utf8. В качестве локали по умолчанию установил русскую. После настроек не забудте поменять кодировку в putty.

Кроме того, в папке созданного пользователя я добавил строчку в файл "~/.bash_profile"
export LANG=ru_RU.utf8

Ну и наконец можно установить часовой пояс на сервере. Сделал я это с помощью команды:
dpkg-reconfigure tzdata

Вот собственно и все. Теперь заливаем на сервер от имени созданного нами пользователя дистрибутив бота с помощью программы WinSCP (ftp сервер я устанавливать не стал вообще, кушает лишние ресурсы и не вполне безопасный). Заходим в putty под этим пользователем и запускаем бот как обычно.

Да, и еще. Базу данных создаем через phpmyadmin, который находится по адресу: http://ip_вашего_vds/phpmyadmin. При этом я создавал новую базу вместе с пользователем mysql. Вписываем эти настройки бота, в качестве адреса сервера mysql указываем 127.0.0.1.

Осталось добавить пару слов насчет памяти. У меня при одном запущенном боте использование памяти составило порядка 100мб. Соответственно тариф можно было выбрать и пониже.