There are lots of ways in which malloc/free can store the size of the memory area. For example, it might be stored just before the area returned by malloc. Or it might be stored in a lookup table elsewhere. Or it might be stored implicitly: some areas might be reserved for specific sizes of allocations.
To find out how the C library in Linux (glibc) does this, get the source code from http://ftp.gnu.org/gnu/glibc/ and look at the malloc/malloc.c
file. There is some documentation at the top, and it refers to A Memory Allocator by Doug Lea.