With Nix, how does the shell search for an executable?

       It searches PATH for the right executable.

   What dirs does it find them in?  

In the `nix store', which is /nix/<HASH>-<PACKAGE>/bin; each program
is linked against the library it was compiled against which is located
in the `nix store'.  So for example, GNU hello 1.0 might look like
this,

/nix/<hash>-hello-1.0/bin/hello       -----+-----+
/nix/<hash>-hello-1.0/lib/libhello.so <----+     |
/nix/<hash>-hello-1.0/share/info/hello.info      |
                                                  |
/nix/<hash>-glibc-1.0/lib/libc.so     <----------+

Where the lines mean ELF shared dependencies (i.e. hello is linked
against libhello.so and libc.so).

   Is it true that /bin does
   not exist as we are used to?  

That is correct, the only thing in /bin is /bin/sh for backward
compatibility.

   If it's true, how is it different
   and why?

I tried to write a condensed description, but it wasn't very good so
I've quoted part of the description from Nix instead.

| Nix is a purely functional package manager. This means that it treats
| packages like values in purely functional programming languages such
| as Haskell — they are built by functions that don’t have side-effects,
| and they never change after they have been built. Nix stores packages
| in the Nix store, usually the directory /nix/store, where each package
| has its own unique subdirectory such as
|
|   /nix/store/r8vvq9kq18pz08v249h8my6r9vs7s0n3-firefox-2.0.0.1/
|
| where r8vvq9kq… is a unique identifier for the package that captures
| all its dependencies (it’s a cryptographic hash of the package’s build
| dependency graph). This enables many powerful features.
|
| * Multiple versions
|
| You can have multiple versions or variants of a package installed at
| the same time. This is especially important when different
| applications have dependencies on different versions of the same
| package — it prevents the “DLL hell”. Because of the hashing scheme,
| different versions of a package end up in different paths in the Nix
| store, so they don’t interfere with each other.
|
| An important consequence is that operations like upgrading or
| uninstalling an application cannot break other applications, since
| these operations never “destructively” update or delete files that are
| used by other packages.
|
| * Complete dependencies
|
| Nix helps you make sure that package dependency specifications are
| complete. In general, when you’re making a package for a package
| management system like RPM, you have to specify for each package what
| its dependencies are, but there are no guarantees that this
| specification is complete. If you forget a dependency, then the
| component will build and work correctly on your machine if you have
| the dependency installed, but not on the end user's machine if it's
| not there.
|
| Since Nix on the other hand doesn’t install packages in “global”
| locations like /usr/bin but in package-specific directories, the risk
| of incomplete dependencies is greatly reduced. This is because tools
| such as compilers don’t search in per-packages directories such as
| /nix/store/5lbfaxb722zp…-openssl-0.9.8d/include, so if a package
| builds correctly on your system, this is because you specified the
| dependency explicitly.
|
| Runtime dependencies are found by scanning binaries for the hash parts
| of Nix store paths (such as r8vvq9kq…). This sounds risky, but it
| works extremely well.