Multivariate biosignals are prevalent in many medical domains. Modeling multivariate biosignals is challenging due to (1) long-range temporal dependencies and (2) complex spatial correlations between electrodes. To address these challenges, we propose representing multivariate biosignals as time-dependent graphs and introduce GraphS4mer, a general graph neural network (GNN) architecture that models spatiotemporal dependencies in multivariate biosignals. Specifically, (1) we extend the Structured State Spaces architecture, a state-of-the-art deep sequence model, to capture long-range temporal dependencies in graph data and (2) we propose a graph structure learning layer to learn dynamically evolving graph structures in the data. We evaluate our proposed model on three distinct tasks and show that GraphS4mer consistently improves over existing models, including (1) seizure detection from electroencephalography signals, outperforming a previous GNN with self-supervised pre-training by 3.1 points in AUROC; (2) sleep staging from polysomnography signals, a 4.1 points improvement in macro-F1 score over existing sleep staging models; and (3) electrocardiogram classification, outperforming previous state-of-the-art models by 2.7 points in macro-F1 score.