Lori,
Whether to book in advance depends on whether there's adequate lead time to get Super Economy or Economy tickets on the express trains. Tickets for those are non-changeable and non-refundable after purchase, but if you're committed to travelling on those specific trains you can save a few bucks. If you'd rather maintain more spontaneity, just buy tickets from a Kiosk on the day prior to or on the day of travel. Tickets on the express trains come with compulsory seat reservations, so the tickets will only be valid for one train, date and departure time.
You can buy advance tickets on the Trenitalia website or at www.trainline.eu. I believe you can use Italo Treno on that route as well, and you can also buy tickets for Italo on the Trainline website.
When you arrive in Verona, I'd suggest using a Taxi from the station to Piazza Bra, so that you can maximize your touring time there.