There is no single answer, because networks (or graphs, as they are called in discrete mathematics) are flexible tools that can be used to model all sorts of relationships between genes, transcripts, proteins, or other entities in biology. (And networks are useful models in many other disciplines too, like sociology.) Depending on the type of network you're considering, there are various experimental methods for determining connections. I give only a couple of examples below. For general information on networks as abstract models, look into graph theory.
Gene regulatory networks
A gene regulatory network is a directed graph where one gene (A) regulates another (B). In this case, the connections between genes are directional and can be represented by arrows A $\rightarrow$ B. Depending on exactly how you define "regulation", a connection A $\rightarrow$ B can mean different things, for example:
- Gene A encodes a transcription factor that binds to gene B. In this case, evidence for A $\rightarrow$ B comes from assays of proteins binding to DNA, such as chromatin immunoprecipitation (ChIP). Large collections of such data are available in databases like Transfac.
- Expression of gene A causes regulation of gene B, by any mechanism (possibly indirectly). In this case, data for an interaction can come from experiments where gene A is induced (forcibly expressed) or suppressed/deleted and the resulting changes in other genes are measured, for example by microarrays or RNA sequencing. A famous early example of this is the "Rosetta" data set on yeast deletion mutants.
Inference of gene regulatory networks is a large and complicated topic that I cannot cover here. It depends on many factors, such as how you model the time dimension (do you have steady state or transient data), and how you parameterize the network to model expression data quantitatively. The review suggested by @CMosychuk looks like a good place to start.
This type of network represents coexpression between genes (or more accurately, between mRNAs or proteins). This is typically a representation of pairwise correlations between genes across some set of conditions, so the data source can be any collection of mRNA or protein level expression data. (Here is one example.) Because correlations are symmetric, connections in this type of network have no direction, and can be represented simply as a link A$-$B (not an arrow). Partial correlations are sometimes used to filter out indirect associations, but still these networks contain no causality information, and should not be confused with the directed type.
Protein-protein interaction networks
These are undirected network models where a link A$-$B means that two proteins interact physically. Data supporting such connections come from various biochemical assays for protein interaction, such as the two-hybrid assay or immunoprecipitation. There are large databases collecting protein-protein interaction data that can be used to build these network models, for example BioGRID.
There are many other types of networks, but this is already a long answer :) As you can see, it's important to be clear on what type of network you are working with. Often the data you have available will determine what network model is suitable --- for example, if you have only a collection of unrelated transcriptome profiles and no causality information, a coexpression network might be the best model.