I have setup a Jenkins controller and I want to add an agent node in the same network. Do I need to install Jenkins on the agent machine? Or can I use any arbitrary machine without having to install Jenkins on it first?
No, you don't need to install Jenkins in any slave machine at all.
You will need, if it is a Linux slave, just SSH access enabled. If it is a Windows machine, then Java and connect with the jar provided by Jenkins or through Java Web client.
On Linux and for Java, Jenkins will download anything he needs.