Tiles is a layout engine that allows you to create re-usable areas of screens (like menus, footers, advert panels and so on). Velocity is a templating language. It makes little sense to compare the two.
Velocity can be used as a JSP/JSTL replacement in the web tier, although it has no dependencies on the servlet API like JSP does. You often find velocity employed as a templating engine for email bodies that applications send out for example.
The 2 main advantages velocity used to have in the web tier over JSP were speed and cleaner syntax. With more recent JSP engines and the standardisation of JSTL, these are probably negated.
Tiles should be compared with Sitemesh, and Velocity with FreeMarker or JSP/JSTL.
Public Key: 0xE855B3EA