Typically, the compiler stores the bytes making up the string in the binary file, yes. From there they are loaded into memory along with the actual code when the binary is run. The space where the code and static data are stored is neither heap nor the stack, but another area in the address space of the process. See data segment and particularly this figure which illustrates a typical memory layout of a process on modern platforms.
This is true for string literals. However, a &str can point to an arbitrary place. Not all &strs are literals. If you obtained your &str from a String, then it will point to the heap. If you obtained your &str from a stack-allocated array of bytes, for example, then it will point to the stack.
The type &str doesn't tell you anything about where it points. This is true for all reference types in general – they point wherever their referent lives, this is not reflected in the type (because it doesn't matter). Even &'static T doesn't imply that T lives in the data segment – you could just as well generate a static reference to heap memory by leaking it.