First make sure you have java installed. I think ubuntu ships with OpenJDK (the ubuntu forums could probably answer any questions about this).
Then go to http://star-made.org/download and select one of the linux downloads.
Go to your downloads folder and run StarMade-Starter.jar. You might have to right-click and select \'run with java\' or something similar from the context menu.
From there just follow the GUI prompts for installing and starting the game.