What is the size requirement for a profile background?

It depends on the resolution of the viewers screen. If yours is 800x600 and someone else is using like 2000x1600 or whatever, it's gonna look fine to you and really really small for him.

So what size should I use

I guess 1152x865 is the most common. I dunno though. Use whatever you want. Everyone is gonna see it differently.