Before you can change text, you need to find it. In an ideal world, roms would store text in ASCII format, just like computers. Unfortunately, very few of them do. When you start working with a rom, you don't know what number represents what letter, so you can't do an ordinary search. You can, however, do a relative search.
A relative search looks for changes from one value to the next. We can use this to find text in an unfamiliar rom. No matter what value represents "A", the value for "B" will be one higher, and so on. B=A+1, C=A+2, etc.
For example, the word "hit" could be stored many different ways in a rom. It could be stored as 68 69 74 (which happens to be normal ASCII format). Or it could be 69 6A 75, or 6F 70 7B, or 08 09 14. No matter what, though, H + 1 = I, so the second byte must be 1 higher than the first, and I + 11 = T, so the third must be 11 higher than the second. Using that fact, we can do a relative search and find the word.
Now would be a good time to get a relative search program, like the one in my Utilities section.
Enough theory. Let's go to the rom. Remember how we changed "crystal" to "tribble"? Let's find the start of that message ("return the/crystal to/the palace/in parapa."). We're going to search for "return". Start up Relative Search and enter the name of your rom. Now we're ready to enter relative values. Here's a table for reference:
1 A 2 B 3 C 4 D 5 E 6 F 7 G 8 H 9 I 10 J 11 K 12 L 13 M 14 N 15 O 16 P 17 Q 18 R 19 S 20 T 21 U 22 V 23 W 24 X 25 Y 26 Z
Turn "return" into a sequence of numbers. R=18, E=5, etc. All you have to do is type in values for each byte, and Relative Search will calculate the relative changes for you. So type: 18 5 20 21 18 14. Press return again and it will search the rom and return all matches.
"Return" appears at two places in the rom, 21 and E76C. (As it turns out, the first one is the "Return of Ganon" from the Game Over screen; the second is the start of the message we're looking for.) Go to both addresses in your hex editor. At E76C, the values are EB DE ED EE EB E7. Try changing the first EB to EC. The text will change to "seturn". You've now found some of the game's text.
More importantly, you now know that EB represents "R", DE represents "E", and so on. EB DE ED EE EB E7 represents "return". (Look back at the last section; ED EB E2 DB DB E5 DE represents "tribble".) Now you know how to hack the game's text using just your hex editor: Just replace each old value with the value for the new letter. But it'll be easier and faster if you use tools such as my script tools or Necrosaro's Thingy. To use them, though, you need a table file.