I've been working on a small API/Library and I realized that I was returning memory that wasn't going to be consistently put on the heap or stack. So my question is this: when I return an object from a function in a Library, should that object be on the heap? If not, where? Smart Pointers?

Depends. When a function returns a c++ class it will return a copy of the object, not the object iteself, so it doesn't matter if the original object is on the heap or the stack. If the function returns a POD array, such as char array then it must be declared in the heap because the array is not copied. When such an array is declared on the stack then the array is destroyed as soon as the function returns, making the array invalid. That is the cause of many difficult to find bugs.

Okay! So you're saying that functions that don't return arrays shouldn't return pointers (even though arrays are pointers, pointers are not arrays)? In the case that I do need to return an array (char* (* for markdown purposes), for example) that array must be on the heap.

Here is an example

char* foo()
   char* ptr = new char[255]72222222;
   return ptr;

int main()
    char* p = foo();
    delete[] p; 

char* foo()
    char array[255];

    return array; // WRONG!

There are a few common options (and it's best to stick to what is common, and thus, most likely familiar to users of the library).

The first important question to ask is: are you targetting an ABI-stable platform? In other words, do you plan to support Windows, or only unix-like systems. If you want to support Windows (i.e., a platform that has no stable C++ ABI), then your library's API will have to be in C (unless you have a header-only library). Otherwise, C++ is also an option.

In any case, the key is responsibility. That is, don't give any to the user. If your library creates an object, it is your library's responsibility to destroy it (the right way) and ensure it will get destroyed. That's the basic principle.

It is not really a matter of heap vs. stack, because the stack is not an option. A function cannot return an object from its stack, because its stack is destroyed upon return from the function. If you return an object from a function, it will be either in the form of a (smart-)pointer to an object that was allocated dynamically (on the heap), or in the form of a value (return-by-value) which is actually on the caller's stack. And if you need to stick to a C API, the caller's stack is an unknown (no stable ABI) so you can only put primitive objects there (int, char, double, pointers, etc.), and if you want to return a C++ object, then it means it will have to be returned as a raw pointer to a dynamically allocated object.

Option 1: C API with opaque pointers
This is by far the most common solution because it applies everywhere, it works reliably. And on Windows, this is virtually the only option (and the option that Win32 API uses too). The idea is pretty simple. Have a "Create" function that returns a raw pointer to a dynamically allocated object. Have a "Destroy" function that takes a raw pointer to a dynamically allocated object and deallocates it. And wrap every function that involves this type of object with C functions that take the opaque pointer to the object, casts it and calls the C++ (member) function.

Option 2: Carefully craft your library to make objects ABI compatible.
This is too long to explain here. Long story short, the C++ standard does provide a number of guarantees with respect to how objects are laid out in memory (ABI), and it is possible to carefully craft library classes to be binary compatible across compilers (and options). This is delicate and strict, and relies heavily on the PImpl idiom (aka the compilation firewall idiom).

Option 3 (Unix-like systems only): Rely on stable C++ ABI, avoid standard library components.
On Unix-like systems (Linux / MacOSX / etc.), there is a de facto standard ABI (Intel Itanium) that all compilers comply to. This guarantees that same source equals same memory layout. You cannot rely on any external library component (including the C++ standard library) for anything at the API (interface) because you cannot guarantee that the user is using the same standard library implementation (i.e., different source means different memory layout). But, you can rely on the user using your library's headers to use your library's dynamic libraries (.so files). So, you are safe as long as you don't use any standard library components (or any other external library components) at the interface.

Option 4: Distribute your library as open-source and require the user to compile it.
If you can distribute your library with the source code (no compiled binaries), then you have very little to worry about. In this case, all the standard guidelines apply, such as using RAII and designing your ownership relationships.
Option 4a: If on Windows, do not allow dynamic libraries (DLLs). On Windows, DLLs are a special kind of beast, and for some technical reasons I won't go into, there is no way you can use them in this option. You have to require the user to compile your library in the form of a static link library (.lib or .a).
Option 4b: If on Unix-like systems, there are no restrictions. Dynamic libraries are tightly coupled at load-time, and don't have the technical issues that make DLLs impossible to use in this case.

Option 5: Provide binaries for all platforms and all compiler versions.
This is really a painful option, but some big important libraries can afford to do this, for example, Qt. This is basically like Option 4, except that you compile your library components for the user, which means you have to compile your library for every possible target platform.

A function cannot return an object from its stack

In c++, yes it can.

class foo


foo somefunction()
    foo f;
    return f;

And on Windows, this is virtually the only option

Yes -- in a DLL. Memory allocated in a DLL is not in the same heap as memory allocated in the application program, therefore all memory allocated in the DLL must be destroyed in the same DLL.

A function cannot return an object from its stack

In c++, yes it can.

In that example, the object "f" is copied into the return value of the function. The return value of a function is a variable residing in the caller's stack frame, not the function's stack frame. So, technically, it is not returning an object from its stack, it is copying an object into the caller's stack. That's an important difference in this particular situation, because if the function is part of a library and the caller is the user of that library, then the operation of copying an object into the caller's stack frame is undefined if the type of the object does not have a guaranteed memory layout (which is generally not guaranteed in C++ because the standard does not specify it (ABI)).

Memory allocated in a DLL is not in the same heap as memory allocated in the application program, therefore all memory allocated in the DLL must be destroyed in the same DLL.

Thanks for pointing that out, it's a very important point that I forgot to mention. And yes, that is one of the main reasons why DLLs must pretty much always use the "Option 1" (although "Option 2" is also possible, but very tricky).