Make a grid setup, with your guttering, and setup JQMasonry to appyl itself to everything in that grid.
Then add image sizes for the sizes of tiles you want using add_image_size in functions.php. You will need to regenerate any existing image thumbnails after this has been done.
Then finally display your posts. Use div elements sized to the right tile size, containing the featured image of the associate tile size.
How will you pick the size? Well aside from picking ti manually in some post meta, you can use the trusty random PHP functions:
http://php.net/manual/en/function.rand.php
So if you’ve got 3 tile sizes ( like the page you linked to ), use rand to generate a number between 1 and 3, then have an array with your tile sizes and pick one:
$tile_sizes = array('small','medium','big');
foreach post
$random_size = rand(0,2);
$chosen_size = $tile_size[$random_size];
Also if using WP_Query or get_postsYou may also want to set a random order when you make your query to further randomise things