How to search for a protein sequence of an specific taxa in NCBI?
Try going to http://www.ncbi.nlm.nih.gov/protein and searching for ' (hemoglobin beta[Protein Name] OR (hemoglobin[All Fields] AND beta[All Fields])) AND "Fish"[ORGN] '.

Search filters can be changed with the panel to the left of the search results.