So my gateway or firewall will know which URL I am trying to open? - More or less, yes, but not "directly" per se. It will not know what your IP address is, hence the anonymity. A proxy is simply another computer that exists between your computer and the internet. For example, if you type in www.google.com in your browser while your device is connected to a proxy, this is what will occur:
The browser will make a TCP packet with an HTTP GET www.google.com request (with sender address as your IP address) and sends it to the proxy server. The proxy application running on the server looks the packet and sees that it is addressed to google. It forwards the packet to google.com, changing the sender address in the TCP packet to its own. From here google does not know that it was you who is using their service, they only see the proxy server using it.
Google receives this packet from the proxy and sends the contents of its website in another series of packets to the proxy. The proxy accepts this packet and forwards it back to you. Boom.
Visually:
Browser -> Proxy -> example.com
So, your gateway is under the impression that it is sending an HTTP request to the Proxy server, NOT example.com. Therefore, if you have example.com 'blocked' on your gateway, the connection will still be allowed to the proxy.
:update - since this appears to be a UltraSurf specific question.
Ultrasurf does not use a DNS. It takes your typical DNS queries and routes them to a static IP, instead of asking for one (much like modifying your HOSTS file or equivalent). That way you are connecting to port 80 on the unblocked IP address 74.125.224.160 (youtube.com), instead of making a disallowed DNS query.