The question is not entirely correct... when you create a new Xcode project, the Xcode project includes a reference to the Foundation framework and other standard frameworks, depending on the particular type of project chosen. If you want to use an additional framework, you must explicitly add it to your project.
When you add a Framework to your Xcode project, it supplies a list of Frameworks to choose from, although you can add a framework from an arbitrary location instead of those listed by Xcode. Xcode retrieves the list of frameworks from the content of "~/Library/Frameworks", "/Library/Frameworks", and "/System/Library/Frameworks". When linking, a framework specified with the "-framework" option to GCC will be resolved from those locations. You can extend the list of locations from which GCC will resolve frameworks given with the "-framework" option by modifying the DYLD_FALLBACK_FRAMEWORK_PATH environment variable.
EDIT:
To answer your second question, the "Cocoa/" is a path. Basically, each Framework bundle has a special folder named "Headers" that contains the headers for that framework. When the Framework is added to an Xcode project, the content of "Headers" are added to the standard header search paths, but with their names prefixed with the name of the framework followed by a slash (i.e. "Cocoa/Cocoa.h" resolves to "/System/Library/Frameworks/Cocoa.framework/Headers/Cocoa.h" and not "/System/Library/Frameworks/Cocoa.framework/Headers/Cocoa/Cocoa.h")