The below assumes you are using the correct term 'transformer' for a heavy mostly metal device that outputs 12VAC from mains voltage. If you actually have a switching wall wart adapter that outputs 12VDC then you can omit the bridge rectifier and large filter capacitors shown below, but the solutions are otherwise the same.
Your transformer will give you 12VAC (RMS) - actually probably more like 14V with a light load. If you add a bridge rectifier and capacitor you'll get approaching 20VDC with no load and more like 14VDC with a heavier load. One approach is to simply use a linear regulator such as an LM7805 to reduce the voltage to 5V. The main issue with that is that it's going to waste 2/3 of the power and get very hot with a 750mA load (and thus will require a large heatsink to not destroy itself).
Another approach would be to buy a module that uses an LM2596 regulator (or build a circuit using that regulator). There are such modules available cheaply from China (eg. eBay)n, though I believe the 'LM2596' is typically a counterfeit.
The schematic would look something like this:
Though you'd probably want to increase C1 to 2200uF/25V or more.
If you buy a module the parts after the bridge rectifier and C1 are in the module. You can also buy kit power supplies that are missing all but the transformer.
The LM7805 circuit would be more like the below (again with C1 increased to more like 2200 or 3300uF/25V).
The LM7805 will need a heatsink maybe 100mm x 100mm 3mm thick aluminum plate or thereabouts.
As is well explained elsewhere on this site (Olin has written a canonical answer) the voltage rating must match your device, but the current rating needs to be the same or higher than your requirement. At 5V 10A power supply will not force 10A through your device if it is designed to draw 750mA at 5V. A 5V 1A supply will also work, but not a 5V 0.5A supply.
The super-easy solution (and this is not a design thing) is to just buy a switching wall plug adapter that outputs 0.75A or more at 5.0V. For example, an Ethernet router power supply that outputs 5V@2A would work just fine. They're cheap and good enough for many purposes (and generally safety-agency approved so you won't likely get a shock from the mains).
A transformer can be both a step up or step down, it just depends on the turns ration and what you consider to be the primary and secondary windings.
What you can do is use a function generator to excite a set of windings and then measure the open circuit voltage on the others windings. This can allow you to estimate the turns ratio and see if transformer will work in your application.
This can give you a better description of how a transformer works and how to do the calculations.
Best Answer
These are called switched-mode or switching power supplies.
Yes, they still have a transformer inside. That's necessary, otherwise the low-voltage side wouldn't be touch-safe.
The transformer is kept very small. That's possible because it works at a very high frequency; the mains voltage is rectified and a high-frequency switcher feeds the transformer. The higher the frequency the better the energy transfer between primary and secondary are. Remember that transformers only work on variations in current/magnetic field, so a higher frequency makes for more changes.
Power supplies like this are not only recognizable by their light weight, they usually accept a wide range of input voltages as well, like 100V to 240V.
edit
This is a clever method which allows using a small transformer:
Here the high frequency comes from two spikes per 50/60Hz period, where a capacitor discharges into the transformer when a small thyristor switches the voltage near its maximum. Due to the brief transfers (once per 10/8.33ms) this is only suitable for low power applications. The schematic shows a 150mW supply.