A great way to do this would be to use Custom Post Types. This tutorial explains almost exactly what you want to do, including the fact that it's based on recipes: http://wpmu.org/easy-guide-to-displaying-custom-post-types-in-your-wordpress-theme/
As far as a search limited to only that custom post type goes, you could modify or duplicate searchform.php like so without having to use a plugin at all:
<form role="search" method="get" id="searchform" action="<?php echo home_url( '/' ); ?>" >
<input type="text" name="s" id="s" value="Enter keywords ..."/>
<input type="hidden" name="post_type" value="recipes" />
<input type="submit" id="searchsubmit" value="Search Recipes" />
</form>
If you have trouble getting this to work, make sure the following is included at the top of search.php :
<?php
global $query_string;
$query_args = explode("&", $query_string);
$search_query = array();
foreach($query_args as $key => $string) {
$query_split = explode("=", $string);
$search_query[$query_split[0]] = $query_split[1];
} // foreach
$search = new WP_Query($search_query);
?>