Thanks to Kindari in the Laravel IRC chat room In the Test setup method just bind the interface to the implementation and then set a private member variable using App::make. See below.
App::bind('FooInterface', 'FooImplementation');
$foo = App::make('FooInterface');
also app() is a shortcut to App::make