how did that first bootstrap get made?
Building (writing and cross-compiling) a bootstrap program is not as daunting as you seem to suggest.
I should point out that I am talking about ARM devices really, I get the basics of loading via BIOS on a typical machine, but lets say we are talking about a custom device?
The BIOS that you refer to is essentially a PC convention. (CP/M also had a BIOS, but is wasn't necessarily in non-volatile memory.) ARM CPUs do not normally have or use a BIOS.
The typical ARM processor in use today is integrated with peripherals on a single IC called a SoC, system on a chip. Main memory, e.g. DRAM, and non-volatile storage, e.g. NAND flash, are typically external to the SoC for maximum design flexibility. But typically there is a small (perhaps 128KB) embedded ROM (read-only memory) to initialize the minimal system components to begin bootstrap operations. A processor reset will always cause execution of this boot ROM. (This ROM is truly read-only, and cannot be modified. The code is is masked into the silicon during chip fabrication.)
Each SoC vendor has its own bootstrap method to get the OS loaded and executing. Some use hardware strapping read through GPIO pins to determine the source of the next stage of the bootstrap sequence. Another vendor may use an ordered list of memories and devices to probe for a bootstrap program. Another technique, is to branch to firmware in NOR flash, which can be directly executed (i.e. XIP, execute in place).
One of the problems of bootstrapping a system that uses DRAM for main memory is its hardware initialization. The DRAM memory controller has to be initialized before code can be loaded into DRAM and executed. So where does this initialization code reside, since it can't be in main memory?
Each vendor has their own solution. Some require memory configuration data to be stored in nonvolatile memory for the boot ROM to access. Some SoCs have integrated SRAM (which does not require initialization like DRAM) to execute a small bootstrap program. Some SoCs use NOR flash to hold a XIP bootstrap program.
Once the bootstrap program has initialized the DRAM, then main memory can be used to load the next stage of booting. That could be a sophisticated boot utility such as U-Boot, or (if the bootstrap program is capable) the Linux kernel. Note that there may be several bootstrap programs or stages that have be performed between processor reset to execution of the OS.
The requirements of booting the Linux ARM kernel are spelled out in the following document: http://www.simtec.co.uk/products/SWLINUX/files/booting_article.html
Older versions of Linux ARM used the ATAGs list to pass basic configuration information to the kernel. Modern versions provide a complete board configuration using a compiled binary of a Device Tree.
Obviously the question of "how do you make a bootstrap?" cannot be answered without some qualifications.
Like the PC BIOS, the boot ROM of SoCs are proprietary and not released (unless you sign an NDA, if at all). But most other boot code is released under GPL or similar licensing, and easily obtainable.
ADDENDUM
Since you now mention that you're using a Zynq 7000 (which uses a Xilinx SoC), Xilinx has a video tutorial on How to build a Linux boot image.
That video confirms what I have already written:
1. The Xilinx SoC has an embedded boot ROM (which is technically the first stage, but is more often ignored or described as stage zero).
2. There are "mode pins" to specify the source of the bootstrap program for the next stage.
3. The boot ROM loads a bootstrap program (which is technically the second stage, but often described as "first" stage), called FSBL, to the embedded SRAM. This program initializes DRAM and loads the next stage, U-Boot.
4. U-Boot executes out of DRAM, and loads the Linux kernel.
The video demonstrates that the FSBL source code can be downloaded from the Xilinx site and cross-compiled in a few steps. There is no "trick" as you allege. The build is a straight-forward configure and cross-compile, which I find simpler/easier than the typical application package.
Perhaps your confusion is based on the ambiguity of the boot medium, i.e. the source(s) of the boot images has(have) not been specified. The video mentions NAND flash and SDcard as possible boot devices.
The boot ROM is directed to read the FSBL image from a source medium as configured by mode pins.
The FSBL (if it's like other bootstraps that I have used) is built to read U-Boot from a configured source medium. There is no runtime alternative.
U-Boot tries to live up to its name ("universal"), and can be configured (using environment variables) to load images (and scripts) from various devices. There's also the interactive option.
Also see the Xilinx wiki on Zynq Linux, which declares that "complete information on the booting of Zynq can be found in the Technical Reference Manual".