I'm building a WCF service that will get deployed to a server running IIS. I can add the service reference from the current solution and use it fine.
If I deploy the service to that particular machine, will I need to re-add the service to the application that consumes it?
No, you just need to change the service URL to match the other machine.
A proxy is generated when you add the service reference and that proxy will work against all servers that host those services - it just needs the right URL.
You only need to update the service refernece when the services exposed changes, e.g. adding a new method or changing a parameter.