Primitive fields are stored as part of the object that is instantiated somewhere. The easiest way to think of where this is - is the heap. However, this is not always the case. As described in Java theory and practice: Urban performance legends, revisited:
Thus, beyond saying "the object is created and the field is there too", one cannot say if something is on the heap or on the stack. Note that for small, short-lived objects, it's possible that the 'object' won't exist in memory as such and may instead have its fields placed directly in registers.
More on escape analysis at Wikipedia. For those willing to delve into papers, Escape Analysis for Java from IBM. For those coming from a C# world, you may find The Stack Is An Implementation Detail and The Truth About Value Types by Eric Lippert good reads (they're useful for Java types also, as many of the concepts and aspects are the same or similar). Why do .Net books talk about stack vs heap memory allocation? also goes into this.
The parameters are part of the stack too. In the situation that you don't have a heap, you would be passing the full set of values on the stack. This is fine for "foo" and small strings... but what would happen if someone put a huge XML file in that string? Each call would copy the entire huge string onto the stack - and that would be quite wasteful.
The advantage of the stack is that when you have a variable that exists with a scope, when you leave that scope, that stack frame is popped. It really simplifies what is there and what isn't. The program moves to another procedure, a new stack frame; the program returns to the procedure, and you've back in the one that sees your current scope; the program leaves the procedure and all the items on the stack are deallocated.
This really makes life easy for the person writing the runtime for the code to use a stack and a heap. There are simply many concepts and ways of working on the code, allowing the person writing the code in the language to be freed of thinking of them explicitly.
The stack's nature also means it can't become fragmented. Memory fragmentation is a real problem with the heap. You allocate a few objects, then garbage collect a middle one, and then try finding space for the next large one to be allocated. It's a mess. Being able to put things on the stack instead means that you don't have to deal with that.
When something is garbage collected, it's gone. But it is only garbage collected because it's already forgotten about - there are no more references to the object in the program that can be accessed from the current state of the program.
I'll point out that this is a very large simplification of garbage collection. There are many garbage collectors - even within Java, you can tweak the garbage collector by using various flags (docs). These behave differently and the nuances of how each one does things is a bit too deep for this answer. You may wish to read Java Garbage Collection Basics to get a better idea of how some of that works.
For the most part, it's tradition. The text books written and compiler classes and various bits documentation make a big deal about the heap and the stack.
The object is somewhere and it's in the place where it can be accessed correctly and quickly for the appropriate amount of time that it exists. Whether it's on the stack or the heap - it doesn't really matter.
