If you buy a Telstra 4G USB dongle it is currently likely to be the ZTE MF821. This is how I got it working on Debian 7.0 (Wheezy).

Connect the dongle to a USB port and run:

$ lsusb
Bus 001 Device 001: ID 1d6b:0002 Linux Foundation 2.0 root hub
Bus 002 Device 001: ID 1d6b:0001 Linux Foundation 1.1 root hub
Bus 003 Device 001: ID 1d6b:0001 Linux Foundation 1.1 root hub
Bus 004 Device 001: ID 1d6b:0001 Linux Foundation 1.1 root hub
Bus 005 Device 001: ID 1d6b:0001 Linux Foundation 1.1 root hub
Bus 001 Device 002: ID 13d3:5702 IMC Networks UVC VGA Webcam
Bus 005 Device 002: ID 0b05:1788 ASUSTek Computer, Inc. 
Bus 001 Device 005: ID 19d2:0257 ZTE WCDMA Technologies MSM

The last line is the one we need.

Using that line as a reference, add the following line into /lib/udev/rules.d/40-usb_modeswitch.rules

# ZTE MF821 4G LTE
ATTRS{idVendor}=="19d2", ATTRS{idProduct}=="0257", RUN+="usb_modeswitch '%b/%k'"

I added it right after the line for ZTE MF820 4G LTE.

Now create a file called 19d2:0257 in /etc/usb_modeswitch.d/ with the following contents:

# Telstra ZTE LTE 4g modem
#
DefaultVendor=  0x19d2
DefaultProduct= 0x0257

TargetVendor=  0x19d2
TargetProduct= 0x0257

MessageContent="55534243123456782400000080000685000000240000000000000000000000"

CheckSuccess=20

So that Network Manager will automatically recognise the device, add the following line to /etc/rc.local

modprobe usbserial vendor=0x19d2 product=0x0257

Now the ZTE MF821 will be recognised as a Mobile Broadband connection whenever it is plugged in.

For GNOME desktop lurve

  1. Right-click on the NetworkManager applet and select "Edit Connections"
  2. Select the Mobile Broadband tab
  3. Click on Add.
  4. Select "My provider uses GSM-based technology" and press OK.
  5. Give the Connection a name ie: Telstra HSPA
  6. Tick connect automatically.
  7. Press Save.

You can know disconnect / reconnect the Telstra 4G USB dongle and enjoy the inter-webs lurve.

For 3G Usage

If you find yourself in a 3G only area, you will need to configure the following for GNOME:

  1. Right-click on the NetworkManager applet and select "Edit Connections"
  2. Select the Mobile Broadband tab
  3. Click on Add.
  4. Select My provider uses GSM-based technology and press OK.
  5. Give the Connection a name ie: Telstra UMTS
  6. Tick connect automatically.
  7. Set the APN: telstra.internet.
  8. Press Save.

Now you should be working fine on 3G too.