I never had this problem until I tried using my 1TB disk to backup my main drive (256gb) plus my extra drive (750gb). So, just 1 to 1. The problem is, for most cases, TM disk should be at least twice as big (as your data).
You probably have a disk that's too small! And you'll be better off either reducing how much data you want to backup, by excluding some folders from it (under TM options), or simply buying a bigger disk. 2 TB disks are quite affordable nowadays, specially if you consider how much it would cost you to lose your data...
Of course, you can also keep manually deleting backed up data to make the message go away every time it appears... But that will beat most of the advantages of automated backup. In fact, if a backup is not automated, you won't do it as often as you should thus making it most likely a useless backup for when you need it, it shall be outdated.
Now... If that's not your case, then there's this one site resource for all things Time Machine. And this is their relevant article about full disks: http://pondini.org/TM/C4.html