Triangles you are seeing are likely just a product of the rendering system -- everything, in the end, has to be broken down into triangles for rendering.
I suggest you do this: search google (images) for "sphere tessellation". You will get an idea of the many, many ways of doing this. Your game does not need to be tessellated in exactly the same way as Populous: The Beginning (which, by the way, is a great game which I love). Meaning you don't even need to use square tiles, if you don't want to; you could use any hexagons, triangles, pentagons, arbitrary quadrilaterals like kites, or even voronoi tessellation (irregular, non-repeated polygons).
What's important in any tessellation used for game logic is connectivity, i.e. the fact that your "grid" forms a (somewhat) connected graph for movement purposes.
EDIT: Probably what they've done is something a little like StarControl's melee -- they actually have a wrapping 2D grid (modulo in x and y). Then, when you view the sphere, you can only see one hemisphere at once, which makes it possible to map the tiles without too much noticeable distortion. And at a closer zoom, all would look perfect.