Nexus 4 running a CM 10.1 nightly. If you open Maps, click the "Directions" button (not nav, sorry), then it'll ask you what you want directions to, and your recent searches will be there.