How does a GLSL sampler determine the minification, and thus the mipmap level, of a texture?

Blocks of adjacent pixels are computed in parallel. (IIRC the PowerVR chips do a 4x4 block at a time, for example.) When you call texture2D in your fragment shader, the sampler is fetching all 16 samples for all 16 pixels at once, and so has adjacency information needed to calculate the minification level. This is part of why it's so important for adjacent pixels to sample from nearby areas of the texture.

Note that this only applies to fragment shaders. In vertex shaders the first mipmap level is always used, (unless you use the Lod version of texture2D is used.)

You are allowed to compute texture coordinates arbitrarily, and the shader will act accordingly... within one restriction. Your computations cannot involve any conditional logic. They can involve varyings, uniforms, constants, values sampled from other textures, whatever you want. But the moment you slip so much as a ?: operator in there (let alone an if-statement), you're in trouble.

And since you're in OpenGL ES land, you don't really have the tools to get yourself out of that trouble. Desktop GL 3.0 gives you the textureGrad set of functions, which allows you to compute gradients before reaching the conditional logic. But without that, there isn't much you can do.