Q:

How do JMP and CALL work in assembler?

If you compile, link and run something like this:
global _start

section .text

_start:
jmp message

proc:
...

message:
    call proc
    msg db " y0u sp34k 1337 ? "

section .data

How does the machine know where he needs to jump? I guess "message:" and "proc:" are translated to adresses.
Do "message:" and "proc:" have absolute or relative addresses? 
If I compiled the programm on my PC and execute it on another PC, how can it work on the other machine? I mean regarding the addresses for "message:" and "proc:". Will it be always a different address?

A:

Yes, they are translated to addresses. There are different jmp instructions for relative or absolute jumps or far or near jumps. The assembler will choose one of them (e.g., the shortest one) and translate the mnemonic (jmp) to the corresponding machine code.
They have relative addresses. The assembler produces an object file, which contains relocatable code and data. It can be combined with other object files by a linker to finally yield an executable. The executable in the end has absolute addresses1.
No. Every process has its own virtual address space, so each process's very first address is 0x00. The addresses used in an executable are virtual too, so they map to arbitrary physical addresses.
Besides, it's obviously required that the PCs have

the same architecture (PC usually means x86)
an operating system using the same executable format/object file format

1 Technically, that's not true. The image may be relocated at load time.

