Cannot say for certain about the North, but the Southern express companies were the rump of the national one before the war, so I expect they worked the same way.
Shipper took the item to the Express Office (almost certainly in the railroad depot, though I have never seen that stated) and paid the fee to ship. Shipper received a receipt. The package rode in a separate express car or in the baggage car. An express company employee rode with the express shipment until it reached the destination. Receiver picked up the package at the Express Office.
Express was used to ship smaller things that had to go through right now --- barrels of peaches, urgently needed supplies (small quantities) and MONEY -- great mountains of currency were shipped in such packages in the South.
Southern railroads made a lot of money from the Express Companies, but (of course) wanted to make more. So several companies in the southeast started their own service to cut out the middleman.