Deep linking is where a link to a site points to something other than the domain root, which is, for example, www.mysite.com, or pages easily accessible from that.
Instead it points to a page or directory much further down in the site structure.
Why Deep Link?
Search engine spiders will often not fully crawl an entire site when starting at the domain root. Having a site map, whether one navigable by users, or one submitted to a search engine through utilities like Google Webmaster Tools, can help here, but adding links to deeper pages in the site is also useful.
Have a look at this site diagram for an example of the navigation construction of a site. Of course, this example is over simplified, as even pages deep into the site will often link "upwards" to pages other than their immediate parent, and will often link "sideways" too. It is, though, a reasonable example of the structure of a site from the top ("root") down.
By starting off further down the site hierarchy, spiders can crawl deeper into a site, potentially indexing more pages. Good internal linking of the site helps here. There is little point deep linking to a page if the spider can't crawl to anywhere but the top level of the site from it. Look at this diagram for an example of "bad" internal linking. The page at the bottom, although it has several parents, only links to the main page, as indicated by the arrows.
BreadcrumbsBreadcrumbs are a common method of internal linking, but additionally, sites like Wikipedia and other wiki have very good internal linking based on contextual links within the page, allowing a search engine spider to find many more pages from the same site.
Your aim with a deep link is to push spiders into the site structure at different levels. This isn't quite as easy as it sounds.
Many sites are still willing to exchange reciprocal links. They will normally only be willing to exchange top-level domain links. Possibly useful, but not deep linking. Similar problems can be found when submitting your site to web directories; again, they are only after top-level links. You need more control over where your links point, but you are still looking for a reasonable amount of "quality" from the linking site.
Article marketing is of course an excellent way of adding deep links to your site, either through your resource box, and within the article itself on sites like InfoBarrel. Other methods include various bookmarking sites, forums and blogs, but if you are posting links to your own content on sites you don't own, don't spam. You may well lose your account, and at the very least will probably have your post deleted.
Link bait, where you create something unique to your site that is good enough that people want to link to it, is one of the best ways of deep linking, but it is completely passive and you need to create content that's good enough for people decide to link to.
Nofollow links aren't useful for steering search engine spiders deeper into your site, but should not be rejected merely for that reason. They may still drive actual traffic.