A very nice program for doing all sorts of photomosaics is in the repositories and is called metapixel.

Install from software-center or open terminal and run

sudo apt-get install metapixel

The readme is available at the github page or from /usr/share/doc/metapixel/README.gz when it is installed, and it notes that

Metapixel is a program for generating photomosaics. It can generate
classical photomosaics, in which the source image is viewed as a
matrix of equally sized rectangles for each of which a matching image
is substitued, as well as collage-style photomosaics, in which
rectangular parts of the source image at arbitrary positions (i.e. not
aligned to a matrix) are substituted by matching images.

The readme contains full instructions for use, but a useful youtube tutorial for Ubuntu exists, as well as a sort of online gui with which you can construct your command-lines.

Nevertheless, here's an example of how I used metapixel to create a classic photomosaic.

There is a perl script that comes with metapixel called metapixel-prepare, and this is very useful for generating the photo tiles that your mosaic image will contain.
Options can be found with metapixel-prepare --help, but basically you just have to specify your folder of pictures and your metapixel library folder.

1) This library folder needs to be created before you run the metapixel-prepare command, so run in terminal

mkdir metapixel_library

2) Then to generate the tiles from the selected folder, the minimum command would have the form:

metapixel-prepare ~/location/of/my/pictures/ ~/metapixel_library 

If you wish metapixel-prepare to recurse through the folders you have to specify -r; if you want the tiles to be a specific size (other than the default 128x128), specify at the end of the command, for example, --width 80 --height 80.

As an example, the command I used was:

metapixel-prepare -r ~/Pictures/canon/metapixel ~/metapixel_library --width 80 --height 80

3) To construct your photomosaic you must specify the location of this library of tiles, specify the image to be metapixelled and designate an output file (which must be a .png file). The input jpg can be any kind of picture and any size (see note on scale below).

I used the following commands in my case:

metapixel --library ~/metapixel_library --metapixel /home/mike/Pictures/canon/2012_02_05/img_0372.jpg output.png

The full options for metapixel can be found by entering metapixel --help, and sometimes you may need to use --scale to increase the size of the output image. I didn't in the case above as my input picture was already 4000x3000.

The results will differ according to which pictures you have chosen for your library and your input picture.

The process will also take a while if you select thousands of pictures for the mosaic, and will also consume a fair bit of memory.

Below is a photomosiac created with my own photos (using the commands above):

: