Getting rid of deleted messages

Solution
Depends on what messaging service you use. It'll be gone from your device, but some services do keep records of these things, ranging from harmless things like send/receive times to the entire message itself.