MipMap
MipMaps are downscaled versions (by powers of two) of a Texture that are automatically created if you select Create MipMaps when importing a texture.
The engine uses MipMaps to reduce jitter on textured surfaces when they're viewed from a distance; this process is called bilinear filtering. When drawing a brush surface on the screen, the engine selects the MipMap that fits best; in fact, different parts of the surface can be textured with different MipMaps. Blending multiple MipMaps is called trilinear filtering.
While the Unreal engine supports Textures up to sizes beyond 256x256, some (older) video hardware can't go higher than that. In order to accommodate that, the engine then simply selects the largest MipMap the hardware can handle and displays that instead. So, feel free to use large textures, but if you do, always create MipMaps for them.
ScriptedTextures, FireTextures and other Dynamic Textures have in principle no MipMaps and thus are restricted to 256x256 pixels. MipMaps also aren't used on meshes, so the same restriction applies for them as well.
Example
Until anyone else uploads this anywhere, download the sample [this location]. I hope it helps somehow 
Bright red is top detail (original texture), lower detail = darker red. The smallest MipMaps (8x8 and lower) are black.
Types of texture that should not have MipMaps
Mipmaps should never be created for any texture that is going to be used for anything Interface-related. Player Portrait images and weapon HUD icons are two examples of this.
Mychaeel: I disagree. MipMaps can greatly enhance the display of a downscaled image; otherwise the video card just skips pixels when drawing a downscaled texture or texture part on the HUD.
Legal: I agree with Mychaeel here - MipMaps are often great for Player Portraits in example, however you should make sure the MipMaps doesn't look like shit. The .dds plug-in for Photoshop allows you to see and edit individual MipMaps of textures. If something can't be done with MipMaps, like sometimes the scope of a sniper rifle, leave it out. But make it a last option.
A note about Terrain Heightmap images: there is absolutely no need to create mipmaps for a G16 heightmap image, as the texture itself will never be seen within the game. Mipmaps are purely aesthetic in their nature, so a good rule of thumb would be: If you can't see it in-game, it doesn't need mipmaps (excepting Interface content as mentioned above of course).
Drak: I generally drop the mips for masked textures, this reduces the mask from being blurred in the distance. Also, 2003 & 2004 have an LODset property found within the texture's properties dialog box under 'Texture' that will decide which mip is best for the engine internally. Just select the appropriate one such as: LODset_Interface. In fact, this property should be set for your level preview screenshots for instance. By default LODset_World is selected upon import.
