As CMOS feature size is reaching atomic dimensions, unjustifiable static power, reliability, and economic implications are exacerbating, thereby prompting for conducting research on new materials, devices, and/or computation paradigms. Within this context, graphene nanoribbons (GNRs), owing to graphene's excellent electronic properties, may serve as basic structures for carbon-based nanoelectronics. In this paper, we make use of the fact that GNR behavior can be modulated via top/back gate contacts to mimic a given functionality and combine complementary GNRs for constructing Boolean gates. We first introduce a generic gate structure composed of a pull-up GNR performing the gate Boolean function and a pull-down GNR performing its complement. Then, we seek GNR dimensions and gate topologies required for the design of 1-, 2-, and 3-input graphene-based Boolean gates, validate the proposed gates by means of SPICE simulation, which makes use of a non-equilibrium Green's function Landauer formalism based Verilog-A model to calculate GNR conductance, and evaluate their performance with respect to propagation delay, power consumption, and active area footprint. Simulation results indicate that, when compared with 7 nm FinFET CMOS counterparts, the proposed gates exhibit 6 × to 2 orders of magnitude smaller propagation delay, 2 to 3 orders of magnitude lower power consumption, and necessitate 2 orders of magnitude smaller active area footprint. We further present full adder (FA) and SRAM cell GNR designs, as they are currently fundamental components for the construction of any computation system. For an effective FA implementation, we introduce a 3-input MAJORITY gate, which apart of being able to directly compute FA's carry-out is an essential element in the implementation of error correcting codes codecs, which outperforms the CMOS equivalent carry-out calculation circuit by 2 and 3 orders of magnitude in terms of delay and power consumption, respectively, while requiring 2 orders of magnitude less area. The proposed FA exhibits 6.2 × smaller delay, 3 orders of magnitude less power consumption, while requiring 2 orders of magnitude less area, when compared with the 7 nm FinFET CMOS counterpart. However, because of the effective carry-out circuitry, a GNR-based n-bit ripple carry adder, whose performance is linear in the carry-out path, will be 108 × faster than an equivalent CMOS implementation. The GNR-based SRAM cell provides a slightly better resilience to dc-noise characteristics, while performance-wise has a 3.6 × smaller delay, consumes 2 orders of magnitude less power, and requires 1 order of magnitude less area than the CMOS equivalent. These results clearly indicate that the proposed GNR-based approach is opening a promising avenue toward future competitive carbon-based nanoelectronics.