/Users/lukas is an "absolute" path. The leading / represents the root directory of your filesystem.
lukas is a "relative" path. As it is not anchored to the root, it means "look for this in the current directory". Unless the current directory is /Users (or some other directory with a lukas in it), this will fail.
So, let's explore your examples, assuming you're in /Users/lukas:
$ cd Documents/
/Users/lukas/Documents
Relative path given => change to the directory "Documents" that's inside /Users/lukas.
$ cd /Documents
-bash: cd: /Documents: No such file or directory
Absolute path given => change to the directory /Documents.
$ pwd
/
This shows that you've now changed the working directory to the root directory, / (though the cd command to do this was not shown).
$ cd Users
/Users
Relative path given => change to the directory "Users" that's inside /.
$ cd /Users
/Users
Absolute path given => change to the directory /Users.
The key each time is that leading /. With it, the path is absolute. Without it, the path is relative. This rule is unambiguous because all absolute paths begin with / (because the root directory is always called /).
Here's some pseudocode loosely describing that algorithm:
MakePathAbsolute(path):
if <path> starts with '/'
return <path>
else
return <current directory>/<path>
The argument you pass to cd goes through this algorithm; the directory you end up changing to is the path that the algorithm returns.
Further reading: