You are supposed to archive them... then they go into that ALL MAIL section... and when you are looking for one... you either click on the filter link... or you type in a keyword.
Your inbox is for new mail only... everything else should be archived.
Yup as Gary vdh said, folders in oulook == labels in Gmail. I use them all the time. Emails from work, MyBB, electricity payments, etc.. are all labelled and then I archive them to remove them from the Inbox view. For most of them I actually have filters setup and there's an option to 'skip the inbox' and go directly to the "folder" / label when new mail arrives. The labels all show up on the left menu so you can easily see when you have new mail in them.
The nice thing about labels is that emails can have multiple labels, e.g. all your bank related emails can go into your 'banking' label but some also into your 'personal' label if you have such labels.
Gmail FTW
On a side note, has anyone noticed some emails coming from googlemail.com, e.g. [email protected] instead of gmail.com?