How is 3D map data typically stored in games and what types of file formats are commonly used? Also are there editors available? Any help would be appreciated, since it seems to be somewhat of an arcane art according to Google.

I would think that 3D maps are stored in some kind of array.

Different games use different formats, usually specific to the way the graphics engine (renderer) works. For example, Quake's engine makes heavy use of BSP trees, so the map format stores level geometry in the form of a BSP tree.

It varies widely based on the game type, what kind of 3D things are being displayed, etc. In Freebuild, for example, the map is a set of data including a list of shapes and coordinates, a sun, lights, a terrain block, and metadata like coordinates of spawnpoints. The actual terrain, the information about each shape in the map, etc are stored in separate files that are loaded into RAM when the map is loaded. I believe that Unreal Tournament follows a slightly different model, where textures and certain static shapes are stored in their own files (but packed together, so all the textures for one map can be in one file, for instance). The actual map file then contains similar data to the Freebuild maps, as well as many of the objects in the map in the form of polygon coordinates and texture coordinates.

If you're storing a terrain, the basic idea is a heightfield (a 2 dimensional array representing heights).

If you're storing anything else you need (at least) 3 coordinates for vertex positioning, and then a set of edges connecting them (basically a graph data structure). Vertex normals (also 3), and texture-mapping coordinates (2) are also common.

But don't forget that if you're potentially going to have objects repeated several times in a map, some way to either define objects separately or use references to existing objects with different base coordinates, scale, and rotation would be a good idea.

If you're storing level data for a game that uses, say, raycasting, where Y dimensions are constant and X and Z lengths are uniform, then you can store level data as a 2D array. Then you can create multiple 2D arrays to get a heightmap. If you have irregular geometric figures in your level, I'd imagine storing the (X, Y, Z) coordinates of the object's vertices relatively and then placing instances of the object in your level. Or you can listen to benryves.

Ideally, I'd like to tilemap on the surfaces of objects.

You mean static textures? Or you want to dynamically change the textures on the objects in realtime?