From the outside, one can only see the length of the exchanged data, i.e. the total length of the request, and the total length of the response (rounded to a multiple of the symmetric cipher block size, e.g. 16 bytes if AES is used; but not rounded at all with RC4). To avoid leaking any information, all requests and all responses should have exactly the same size; so the padding should have a variable size which depends on the length of the padded data. If you add padding with a random length but with a probability distribution which does not depend on the size of the padded request or response, then the original request length can be reconstructed statistically if that request is performed on a regular basis.
There is no need for the padding bytes to be random. Only the length is visible "from the outside". You can use constant byte values (e.g. a custom HTTP header
X-Padding: ZZZZZZZZZ with, as contents, a sequence of
'Z' of appropriate length). Using random data could actually leak extra information through timing (if the random generator is not very fast, the attacker could observe the client or server reaction time and deduce the size of the padding, thus indirectly obtaining the true request or response length).
Always targeting a fixed size is wasteful of network bandwidth, because all requests will have the size of the largest possible request, and all responses the size of the largest possible response. @Paŭlo's suggestion of padding up to the next multiple of a given value (e.g. up to the next length which is a multiple of 500 bytes) is appropriate: it leaks a bit more than always padding to the same length, but it does not leak much; and it avoids wasting network resources.