JavaScript Symbol type: (non-string object keys)

I thought object keys were strings only

You're right, but that was true for EcmaScript 5 only. ES 6 / harmony is a draft for something new!

I'm trying to make sense of the spec

It's a draft only, rapidly changing. How symbols are used and whether or how they can be created by arbitrary scripts does not seem to have settled yet (scan through the versions for changes).

If you scroll down to the very end of that document (even below Annex F), you for example will see a Section 8.4.4: Symbol Exotic Objects that has been moved out there. It states

Exotic Symbol objects provide alternative definitions for all of the essential internal methods.

You can see them used at section 8.1.7.4 Well-Known Symbols and Intrinsics for example. For proposed uses (and still existing problems / open questions) of Symbol constructors have a look at these strawman pages or this wiki site.