I know that this is a very old question, but the answers to it are just so incredibly incomplete and it is a top search result.
So, there are a few prerequisites for PSEXEC to work against a machine. Mainly, these are..
On a non-domain join computer, you must have a local admin user. You will use that username when connecting to the machine via psexec.
If the computer is domain joined, then you will want to use either a local administrator on the target machine or a domain administrator account.
The machine must have the administrative share open on the computer and the user you are connecting as must have permissions to the share. (Administrators)
You must have certain firewall rules in place. (Again, something that is normally turned on on a domain join.)
It's pretty common that, even on domain joined machines, there are issues with the domain machine's admin shares or issues where sharing isn't working. In windows Vista and above, a common cause is that there were some additional security/filtering measures introduced and certain registry keys didn't get switched on/added when the computer was domain-joined. You can see how to fix that issue here:
The other issue that tends to crop up a lot is the one where firewall rules need to be added. The particular rule you would set to "Allow" in the windows firewall is "Remote Service Management".
To both add that registry key and add the firewall rules, you can run the following commands.
reg add HKLM\SOFTWARE\Microsoft\Windows\CurrentVersion\Policies\system /v LocalAccountTokenFilterPolicy /t REG_DWORD /d 1 /f
netsh advfirewall firewall add rule name="PSExec TCP" dir=in action=allow protocol=TCP localport=445
netsh advfirewall firewall add rule name="PSExec UDP" dir=in action=allow protocol=UDP localport=137