The problem with fishing expeditions is this: if you test enough hypotheses, one of them will be confirmed with a low p value. Let me give a concrete example.
Imagine you have are doing an epidemiological study. You have found 1000 patients that suffer from a rare condition. You want to know what they have in common. So you start testing - you want to see whether a particular characteristic is overrepresented in this sample. Initially you test for gender, race, certain pertinent family history (father died of heart disease before age 50, …) but eventually, as you are having trouble finding anything that "sticks", you start to add all kinds of other factors that just might relate to the disease:
- is vegetarian
- has traveled to Canada
- finished college
- is married
- has children
- has cats
- has dogs
- drinks at least 5 glasses of red wine per week
Now here is the thing. If I select enough "random" hypotheses, it starts to become likely that at least one of these will result in a p value less than 0.05 - because the very essence of p value is "the probability of being wrong to reject the null hypothesis when there is no effect". Put differently - on average, for every 20 bogus hypotheses you test, one of them will give you a p of < 0.05.
This is SO very well summarized in the XKCD cartoon http://xkcd.com/882/ :
The tragedy is that even if an individual author does not perform 20 different hypothesis tests on a sample in order to look for significance, there might be 19 other authors doing the same thing; and the one who "finds" a correlation now has an interesting paper to write, and one that is likely to get accepted for publication…
This leads to an unfortunate tendency for irreproducible findings. The best way to guard against this as an individual author is to set the bar higher. Instead of testing for the individual factor, ask yourself "if I test N hypotheses, what is the probability of coming up with at least one false positive". When you are really testing "fishing hypotheses" you could think about making a Bonferroni correction to guard against this - but people frequently don't.
There were some interesting papers by Dr Ioannides - profiled in the Atlantic Monthly specifically on this subject.
See also this earlier question with several insightful answers.
update to better respond to all aspects of your question:
If you are afraid you might be "fishing", but you really don't know what hypothesis to formulate, you could definitely split your data in "exploration", "replication" and "confirmation" sections. In principle this should limit your exposure to the risks outlined earlier: if you have a p value of 0.05 in the exploration data and you get a similar value in the replication and confirmation data, your risk of being wrong drops. A nice example of "doing it right" was shown in the British Medical Journal (a very respected publication with an Impact Factor of 17+)
Exploration and confirmation of factors associated with uncomplicated pregnancy in nulliparous women: prospective cohort study, Chappell et al
Here is the relevant paragraph:
We divided the dataset of 5628 women into three parts: an exploration
dataset of two thirds of the women from Australia and New Zealand,
chosen at random (n=2129); a local replication dataset of the
remaining third of women from Australia and New Zealand (n=1067); and
an external, geographically distinct confirmation dataset of 2432
European women from the United Kingdom and Republic of Ireland.
Going back a little bit in the literature, there is a good paper by Altman et al entitle "Prognosis and prognostic research: validating a prognostic model" which goes into a lot more depth, and suggests ways to make sure you don't fall into this error. The "main points" from the article:
Unvalidated models should not be used in clinical practice
When validating a prognostic model, calibration and discrimination should be evaluated
Validation should be done on a different data from that used to develop the model, preferably from patients in other centres
Models may not perform well in practice because of deficiencies in the development methods or because the new sample is too different from the original
Note in particular the suggestion that validation be done (I paraphrase) with data from other sources - i.e. it is not enough to split your data arbitrarily into subsets, but you should do what you can to prove that "learning" on set from one set of experiments can be applied to data from a different set of experiments. That's a higher bar, but it further reduces the risk that a systematic bias in your setup creates "results" that cannot be independently verified.
It's a very important subject - thank you for asking the question!