Internet challenges can mean many things. I will consider two main areas here - searching and 'spoofing'.
There are many searching challenges around - some easy and some very difficult. A large part of it can be luck but knowing how to use search engines to your advantage is useful - and Fravias Searchlores contains more than enough information on searching. Taking an hour or so to learn how to search will be beneficial to you in the long run - become familiar with the advanced options of your search engine. Given a search challenge I will normally start with a simple search. I will perhaps try some phrases in quotes. I will always check the first few pages and based on what is returned I will refine my search. If too few sites come back then change your phrases to be a bit less restrictive and if too many come back then change them to exact phrases (ie in quotes in google like "this exact phrase"), and exclude anything thats pure dross. For example, suppose we are searching for a crack for something and we get back a lot of the xxx/warez popup waste of time type sites, simply add -xxx or -warez to your search and say goodbye to them.
If you are doing some cracking/crypto challenge and the program uses a lot of constants then try searching the net for them - is it a specific constant thats being used and part of a standard algorithm like Tea encryption for example ?
OK, on to spoofing. If there is one program that you will want here it is Proxomitron. Easy to use, it acts as a go-between for your page requests and web site replies. You set the proxy in IE to 127.0.0.1 (ie yourself) and proxomitron forwards your requests to the website. Within proxomitron you have the log window (where you can see the detail of the request and the reply). A favourite place of challenges for hiding information is in these headers. Look out for base64 information in the cookies, which will appear in this log window. You can decode base64 strings here.
Many challenges can be completed through carefully altering headers and requests in Proxomitron. You can save a web page with a form to your hard drive and change it (for example to widen a field and allow you to enter longer strings, or to alter a fixed variable), then you can change the referrer using proxomitron so it looks like the original site page made the request. Thats the power of Proxomitron. Other changes which can be made are things like cookie information. If you really want to learn a lot more then you should read the rfc.
One of the things that proxomitron cannot do is to change your IP. To change where it looks like you are from (unless the challenge checks some of the simple HTTP headers) you need other methods. Any page that checks the REMOTE_ADDR variable will find your IP address. REMOTE_ADDR is where the response is sent back to, it is available to server side scripts as a variable, and from there a reverse lookup will give a name for your IP. The easy way to affect this is with an anonymous proxy. You can find lists of proxies on the web but expect to try many out before you find the anonymous one that you want. Cyberarmy used to ask for a challenge to be completed with a .su proxy, although the .su check was only on part of the host name, so blah.super.org would do it. However it was possible to find a proxy like somewhere.at.su which gave a forward lookup to say 188.8.131.52 and then the reverse lookup of that was blah.blah.ru and it didnt work for you :) Still following me ? Many sites ask for specific countries to be used, so you need to know what the country code is for that country, and then find an anonymous proxy with a reverse lookup to that country code (again sites often have testing facilities to find if a proxy is anonymous and it is better to use their testing facilities rather than your own). If a proxy is not anonymous then chances are that it wont work on the challenge as your IP will be passed to it anyway. There are other ways to do these challenges, but none of them are easy. You can change your own reverse lookup information if you have the authority to do so, but most ISP users will not have this authority. There are hacks that can do things like poisoning DNS caches, but to be honest, it is difficult to get them to work when most DNS servers are pretty secure these days, and flooding DNS servers will most likely get you in trouble. Anyway, start simple, watch how many people pass the challenge, and glean what you can from what they post in the forums.
One word of warning regarding proxies - often they are open to the world in error and it is not your right to use them. They are normally found by people scanning for them and if overused then they are often shut down quickly. Although you appear anonymous on the other side you can bet that the proxy server keep logs of what you do, so be careful and do not abuse them.
2012 update - The current tool of use is Firefox with it's two three excellent add-ons: tamper data, cookies manager and firebug. With firebug you can change the code of a page on the fly, and so change forms to post to different pages, or increase field lengths. With tamper data you have some control over the data that is being submitted to a page, as well as some of the header fields like referer. Cookies manager allows changes to cookie values.
I've listed the google hacks book below, it is quite interesting. So you think to search for something is just typing a few words onto googles main page and hope something shows up ? Well this book will show you a whole lot more from advanced searching to scripts and the google API.