Most modern systems have a Memory Management Unit, or MMU. The MMU is responsible for translating physical addresses to virtual addresses. This is used to give each process its own private virtual memory. One process' address X is not the same as another process' address X. This improves performance, security, and reduces the risk of crashes, but it also has the benefit of being usable to implement ASLR. While data may be placed in non-random addresses in physical memory, the system is free to place the data anywhere it wants in a process' virtual memory.
When a process is first created, the only real memory it has access to is the stack, which is limited and is not meant to be used for general purposes. Whenever a non-trivial amount of memory is required, the process needs to use the heap. The only way to do this is to request memory from the kernel via a system call. This system call is given a few arguments specifying the amount of memory it wants, the type of memory, etc. The call returns the base address of some freshly allocated memory of the size specified. One of the things ASLR does is cause this base address to be unpredictable. When ASLR is disabled, allocated memory is placed in predictable locations.
ASLR does more than just randomize the base of allocated memory. When a binary is executed, the dynamic linker connects it to all the shared libraries it needs. Although any given library is kept in only one place in physical memory, the system is able to translate it to a virtual address for each process that uses it. This address translation is done for efficiency reasons, but ASLR makes additional use of it by ensuring the virtual address is random. An executable specially compiled as a Position-Independent Executable (PIE) can call library functions even though the library's base address is randomized.
This is not all ASLR does, and certain security-focused operating systems (OpenBSD, HardenedBSD, Linux with grsecurity/PaX patches, etc.) use a form of ASLR that does even more.
