This could be a google redirect issue. See:
http://www.thesafemac.com/eliminating-browser-redirects-and-advertisements/. There is some good and relevant information here.
Merely clearing the history and cookies and/or resetting the phone won't get rid of this. Been there done that. Also, while I strongly recommend enabling parental controls on your router, using OpenDNS (I do) and blocking specific categories (I do), this is only a band-aid and not a solution. The root cause is still there. Sure, porn sites might be blocked, which I consider to be a very good thing, depending on what the issue is, your personal information can be at risk.
I recommend logging into your router's GUI (the administrative web page). The actual IP address will vary depending on router manufacturer. Check your documentation or search for it. If you haven't changed the default username and password combination to log into your router, please change it! Login to the router and check your DNS (Domain Name Server) Server Settings. See what the IP addresses are (there are two; a primary and a secondary) and go to arin.net to find out who those DNS server addresses belong to. For example, you might have 209.18.47.61 and 209.18.47.62. Those belong to Time Warner Cable. OpenDNS DNS server IPs are 208.67.222.222 and 208.67.220.220. If your DNS IPs resolve to something very odd (a foreign country or something other than your ISPs DNSs, then you need to change those.
My sister-in-law is currently experiencing this problem on her iPhone5. She also has a Mac and a PC. The Mac is essentially used to stream iTunes throughout the house and other entertainment purposes; however, the PC is what she uses to browse the Internet, pay the bills, etc (yes, I stated that correctly). The PC was heavily infected with adware and spyware. One of them was the Trojan.Alureon, which is also known as TDSS, which intercepts network traffic and redirects search engines.
I'm not sure how her Safari browser is being redirected on her iPhone, since there isn't an obvious issue with the phone. I think it started on the Windows PC and the trojan changed the DNS settings on the router or perhaps changed the Hosts file, which is causing the search redirects.
I have not checked the router settings or the Hosts file yet. I was just notified of this yesterday and spent some time late last night cleaning up the PC and trying to troubleshoot the iPhone.
Tonight, I'm going to use my packet sniffer software to take a look at the traffic as she is browsing (assuming her DNS settings were changed to something malicious or mischievous). I'm curious to see what is happening on the wire.
I'm also going to change the default login credentials for her router admin page and make sure that the option to allow remote management is OFF.
Her PC is functioning much better and for the most part is free of adware/scumare/malware; however, there are still some symptoms left behind from these programs. More work to do yet.