Minecraft wiki entry for VPS, associated text: Install minimal xserver stack:
sudo apt-get install xvfb libgl1-mesa-swx11 libxcursor1 libxrandr2 libxxf86vm1
For testing purpose install mesa-utils and try xvfb-run glxinfo and xvfb-run glxgears:
apt-get install mesa-utils and try xvfb-run glxinfo xvfb-run glxgears
Also test with xvfb-run -a xrandr. If you get this error:
/usr/bin/xvfb-run: 182: xrandr: not found
install x11-xserver-utils like so:
sudo apt-get install x11-xserver-utils