I just got the 2018 Sixth Edition of the book, _Linux in Easy Steps_, and on pages 22-23 it suggests using a USB memory stick ("thumb drive") as a backup medium. I deleted all the Windows files from a 64GB Patriot thumb drive, but it still has the Windows file system on it. When I tried to back up Linux to it I got the message, "Selected device does not have Linux partition."

How do I add a Linux partition to the USB memory stick?

You can just use a partitioning utility to do it, there are several of them available. Gparted is a popular utility, and it can also format a newly created partition with a filesystem too (including both Linux and windows filesystems).

How exactly are you trying to "back up Linux to it" though? As you would normally use a program to backup an operating system rather than just copying the files manually.

A lot of the memory sticks you buy these days aren't partitioned at all. They just have one single Windows FAT32 filesystem stretching across the whole drive. There are about three different ways that I can think of to back up onto a drive like that:

1) jsb's suggestion. Use gparted to create a partition table on the stick and make one or more linux partitions on it. This is the most flexible solution. For example, you could use one of those partitions for a periodic backup of your system and another for day-to-day data file backups.
2) Use the mkfs.ext4 program to turn your unpartitioned stick into a single Linux filesystem which you can then dump onto. This is a bit more dangerous because you have to be very sure you are formatting the stick and not any part of your hard drive. In Linux as in Windows, formatting destroys data!
3) Use the modprobe command to load the vfat driver into your kernel. You should then be able to copy onto your stick as is. This is probably the safest way, but tiresome as you have to do it each time you make a copy.

It'll likely make your learning a bit easier if you put an ext4 file system onto it.

(You can save some extra MBs by using the -m option when creating it, I use -m0 for small drives.)

While I know floppy disks don't have partitions; I don't honestly buy the argument that "some USB sticks don't have partitions at all". Surely there would still be at least one partition that, in that case, covers the whole drive. How would you format a USB drive with a filesystem that isn't partitioned? I don't see how you would able to.

You format /dev/sdb or whatever.

Remember that /dev/sdb is the device. /dev/sdb1 would be the partition.

I have never seen a flash drive that did not have a partition. Yes, they usually have a single vfat partition, but always have a partition when purchased new.

@pathfinder027
As was said before, partitioning can be done with any of the partitioning tools, and gparted is the gui version of parted. You probably have parted, fdisk, and possibly gdisk available with a new install. gparted may need to be installed. Any of those can be used to change the partition type from msdos to linux.
Gparted can also do the formatting as ext4 or you can use mkfs.ext4 to format it for you. Remember, the partition (ie. /dev/sdb1) is what needs to be formatted, not /dev/sdb.

I have not purchased a USB drive without being partitioned in awhile and can not say that it is still true but yes as an example Imation which no longer exists sold flash drives without partitions. They mounted on both linux and Windows without any problems.

We expect a drive to be partitioned by convention and for various reasons but it does not matter. I know formatting ext filesystems actually reserves the first sector so that grub can be installed without a partition table. Totally unrelated but DVRs in the early days wrote video data to an unformatted raw disk for performance.

It's easy to find out one way or another. Plug in your device and look at dmesg|tail. If it reports both sd? and sd?1, there is a partition table on the device. If only sd?, there isn't.

Same here.

That's always been the case as far as I've seen.

I just plugged in the most recent one I bought and it says:
See? No partition table on that one.

It is possible.
I just did on a USB stick. Or fat.
And it's usable.
I've also created encrypted USB sticks like this.