Baking normal maps in blender: "Error: No objects or images found to bake to"
Cycles
Cycles bakes to the last selected image texture node in the object's material. Note that the node doesn't need to be connected to anything.
Blender Internal
This one is a bit confusing and non intuitive. You are mostly correct, you must assign all the faces to the texture as a Face texture.
This is done by selecting the target image in the UV image editor while all faces are selected in edit mode.