This post answers specifically the title question:

> How does ``Needs["foo`"]`` find the file that defines context ``"foo`"``?

----

`Get`, `Needs`, `Install`, `OpenRead`, etc. all use [`FindFile`](http://reference.wolfram.com/language/ref/FindFile.html).  How `FindFile` resolves file names is discussed in:

 * [`FindFile`](http://reference.wolfram.com/language/ref/FindFile.html), Details section

 * [Naming and Finding Files](http://reference.wolfram.com/language/tutorial/NamingAndFindingFiles.html)

 * [Files for Packages](http://reference.wolfram.com/language/tutorial/FilesForPackages.html)

----

I don't know the *full* details (it's complicated), but roughly `FindFile` translates a *context* to a *file path* as follows:

``FindFile["foo`"]`` either

 - Looks on `$Path` for `foo.m`, `foo.wl`, `foo.mx` or directory `foo`
 - If a paclet declares the context ``foo` `` in its `Kernel` extension, it translates to the corresponding `Root` directory: See http://mathematica.stackexchange.com/q/132064/12, Kernel extension section.

Then if the result was a directory `dir`, it continues to look for

 - `dir/init.m` (or `init.wl`)
 - `dir/Kernel/init.m` (or `init.wl`)

If the result was a directory `dir.mx`, it continues to look for

 - `dir.mx/$SystemID/dir.mx` (insert the value of [`$SystemID`](http://reference.wolfram.com/language/ref/$SystemID.html))

This is useful because `.mx` files are not compatible across different platforms.

----

`FindFile["foo"]`, where `foo` is not a context, 

 - Looks on `$Path` for `foo`.

If the result is a directory, then it continues to look for

 - `foo/$SystemID/foo`

This is useful with [`Install`](http://reference.wolfram.com/language/ref/Install.html), when we need a separate executable for each `$SystemID`, but we want to be able to use the same name to refer to them on any platform.

----

### Notes

The context of a package, i.e. the context given in `BeginPackage` that will contain the public package symbols, *does not play any role in how `FindFile` resolves a context name to a file path*.

However, `Needs` is different from `Get` in that it expects the context passed to it to appear in `$ContextPath` after the package has been loaded. This is why one needs to use [`BeginPackage`](http://reference.wolfram.com/language/ref/BeginPackage.html) and not merely [`Begin`](http://reference.wolfram.com/language/ref/Begin.html) when writing a package.  `BeginPackage` will also add that context to `$Packages`. `Needs` uses `$Packages` to determine if a package has already been loaded and avoid double-loading.  

<sup>(Something interesting: `BeginPackage` also updates ``Internal`$PackageDependencies`` based on its second argument. I do not know where this is used.)</sup>

In short, the file names and the context of a package doesn't strictly need to be the same.  But if it isn't, Mathematica will get confused.

All the rules above explain why the standard application directory structure is as described [here](http://mathematica.stackexchange.com/a/124599/12).  There is nothing strictly enforcing this particular structure, but the system is designed in a way that it expects to find structure in any package.