The trick was sending other data over SMS using UDH, that is invisible to user.
User Data Header (UDH) is a binary structure which may be present at the start of a short message in the Short Message Service in GSM. It does not contain any text, but it specifies how the message should be formatted and processed.
Enhanced Messaging Service (EMS)
EMS is an intermediate technology, between SMS and MMS, designed to work with existing networks.
An EMS enabled mobile phone can send and receive messages that have special text formatting (such as bold or italic), animations, pictures, icons, sound effects and special ring tones.
Do you remember all these black and white background images on your old Nokia? Yes, these were sent using plain old regular SMS with special UDH!
Also, when you sent a contact data to another number in vCard format, it was delivered using UDH and XML formatted data. Unfortunately this is also no more supported in some smartphones.
What is still being used
Although text formatting and ring tones data is ignored on smartphones, SMS User Data Header is still very widely used.
Multipart text messages
One good example is multipart SMS. When your text message exceeds 160 characters, the SMS is actually sent in multiple separate text messages with special UDH, so that your phone can merge separately sent SMS messages to one big text.
Take a look at SMS length calculator to see, how it actually works!
Voice Mailbox status
All these notifications about Voice Mail messages and Voice Mailbox statuses are sent using special SMS UDH header.
SIM toolkit is used for some special applications, that use binary SMS for various special cases, for example secure encrypted user identification.