This is of course a judgement call depending on just how grim it looks and how large it is. But I would start with filling it with warm water and PBW, let it sit for an hour and then give it a serious scrubbing. When done rinse out the PBW and sterilize the barrel.
Sterilization (or at least disinfection) can be done in several ways. In this case my method of choice, if applicable, would be heat. If you by any chance have access to a source of dry heat (e.g oven) large enough for the job then 170°C for 2 hours (+ time for the barrel to warm up) would properly sterilize the barrel (given that it actually became clean after your scrubbing).
If this is unfeasible I would turn to wet heat (i.e. boiling). This may also pose some major problems if the barrel, as i suspect, is large. It would require that you have something to bring the filled barrel to boil, for example an immersion heater or a water heater element, but please do not electrocute yourself!If you do have access to this then a sterilization method called Tyndallization would be recommended. Tyndallization, rather than just boiling will ensure that spores and not just bacteria is killed, despite the vague statement of efficiency in wikipedia this is taught at my university to be a method of proper sterilization, and I would thus trust it to be adequate for home-brewing purposes.
If this too turns out to be more trouble than it is worth then I would go for chemical disinfection. Bleach would do the job but I'm afraid it may be hard to rinse out properly and may spoil your cider, so StarSan is probably the safer choice. Fill the barrel up, add an appropriate amount of StarSan (see label) and leave it for about an hour. This is however not a method of proper sterilization. It will hopefully be good enough for our purposes, but sample your first batch with a bit of care.
Disclaimer: I have never myself attempted such a thing and have no experience of barrel cleaning, so there may be better ways.